题解 P1165 【日志分析】

medusa · 2013-06-26 09:47:18 · 题解

首先我说一下题目大意：我们可以把题目看成一个栈，而题目的要求就是在这个栈里面进行入栈、出栈和查询的工作。

解题思路：我们设f[i]为栈中从下到上的i个元素中的最大值，当我们加入一个新元素x时，t++，由于多了一个元素，所以f[t]=max(f[t-1],x)。那么在出栈时只要输出f[t-1]，在查找时只要输出f[t]。

参考代码：

#include<iostream>   
#include<cstdio>   
#include<cmath>   
using namespace std;   
int f[200001],n,x,y,t=0;   
int main()   
{   
    cin>>n;   
    f[0]=0;   
    for (int i=1; i<=n; i++)   
    {   
        cin>>x;   
        if (x==0)    
        {   
                  cin>>y;   
.                  t++;   
                  f[t]=max(f[t-1],y);   
        }   
        if (x==1) if (t!=0) t--;   
        if (x==2) cout<<f[t]<<endl;   
    }   
  //  cin>>n;   
    return 0;   
}