P1165 日志分析

题目描述

M 海运公司最近要对旗下仓库的货物进出情况进行统计。目前他们所拥有的唯一记录就是一个记录集装箱进出情况的日志。该日志记录了两类操作：第一类操作为集装箱入库操作，以及该次入库的集装箱重量；第二类操作为集装箱的出库操作。这些记录都严格按时间顺序排列。集装箱入库和出库的规则为先进后出，即每次出库操作出库的集装箱为当前在仓库里所有集装箱中最晚入库的集装箱。

出于分析目的，分析人员在日志中随机插入了若干第三类操作――查询操作。分析日志时，每遇到一次查询操作，都要报告出当前仓库中最大集装箱的重量。

输入输出格式

输入格式：

 

包含N+1 行：

第一行为1 个正整数N，对应于日志内所含操作的总数。

接下来的N 行，分别属于以下三种格式之一：

格式1: 0 X //一次集装箱入库操作，正整数X表示该次入库的集装箱的重量

格式2: 1 //一次集装箱出库操作，（就当时而言）最后入库的集装箱出库

格式3: 2 //一次查询操作，要求分析程序输出当前仓库内最大集装箱的重量

当仓库为空时你应该忽略出库操作，当仓库为空查询时你应该输出0。

 

输出格式：

 

输出行数等于日志中查询操作的次数。每行为一个正整数，表示查询结果。

 

输入输出样例

输入样例#1：

 

130 10 220 40 221211212

输出样例#1：

 

24410

 

 

 

 

 

 

 

 

 

说明

对于20%的数据，有N≤10；

对于40%的数据，有N≤1000；

对于100%的数据，有N≤200000，X≤10^8。

简单的栈模拟？？No，这样只能得49分，这个题得正解是单调栈，通过题目可以知道我们要求所处栈中最大的，那么小的一定是没有用的，那么我们再输入的时候，仅储存到当前位置最大的，然后在输出的时候直接输出即可

49分代码：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int n,m,x,stack[200001],top,maxl;int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)    {        maxl=0;        scanf("%d",&m);        if(m==0)        {            scanf("%d",&x);            stack[++top]=x;                    }        if(m==1)          top--;        if(m==2)        {            for(int j=1;j<=top;j++)              if(stack[j]>maxl)               maxl=stack[j];            printf("%d\n",maxl);        }    }    return 0;}
          
         
        
       
      

 

满分代码：

#include
     
      #include
      
       #include
       
        #include
        
         #define N 200010using namespace std;int n,p,x,top,stack[N];int read(){    int x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();    return x*f;}int main(){    n=read();    while(n--)    {        p=read();        if(p==0)        {            x=read();            if(x>stack[top])stack[++top]=x;            else stack[++top]=stack[top-1];        }        if(p==1) top--;        if(p==2)         printf("%d\n",stack[top]);    }    return 0;}