P1165 日誌分析

題目描述

M 海運公司最近要對旗下倉庫的貨物進出情況進行統計。目前他們所擁有的唯一記錄就是一個記錄集裝箱進出情況的日誌。該日誌記錄了兩類操作：第一類操作為集裝箱入庫操作，以及該次入庫的集裝箱重量；第二類操作為集裝箱的出庫操作。這些記錄都嚴格按時間順序排列。集裝箱入庫和出庫的規則為先進後出，即每次出庫操作出庫的集裝箱為當前在倉庫里所有集裝箱中最晚入庫的集裝箱。

出於分析目的，分析人員在日誌中隨機插入了若幹第三類操作――查詢操作。分析日誌時，每遇到一次查詢操作，都要報告出當前倉庫中最大集裝箱的重量。

輸入輸出格式

包含N+1 行：

第一行為1 個正整數N，對應於日誌內所含操作的總數。

接下來的N 行，分別屬於以下三種格式之一：

格式1: 0 X //一次集裝箱入庫操作，正整數X表示該次入庫的集裝箱的重量

格式2: 1 //一次集裝箱出庫操作，（就當時而言）最後入庫的集裝箱出庫

格式3: 2 //一次查詢操作，要求分析程式輸出當前倉庫內最大集裝箱的重量

當倉庫為空時你應該忽略出庫操作，當倉庫為空查詢時你應該輸出0。

輸出行數等於日誌中查詢操作的次數。每行為一個正整數，表示查詢結果。

輸入輸出樣例

13
0 1
0 2
2
0 4
0 2
2
1
2
1
1
2
1
2

2
4
4
1
0

說明

對於20%的數據，有N≤10；

對於40%的數據，有N≤1000；

對於100%的數據，有N≤200000，X≤108。

這題有點像單調棧？

因為每次詢問最大值，所以我們只要保存最大值就可以了

比最大值小的數不需要

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 const int MAXN=10000001;
 7 int n,p,now,maxn;
 8 int read(int & n)
 9 {
10     char c='-';int x=0;
11     while(c<'0'||c>'9')c=getchar();
12     while(c>='0'&&c<='9')
13     {
14         x=x*10+(c-48);
15         c=getchar();
16     }
17     n=x;
18 }
19 int s[MAXN];
20 int top=0;
21 int main()
22 {
23     read(n);
24     while(n--)
25     {
26         read(p);
27         if(p==0)
28         {
29             read(now);
30             s[++top]=max(now,s[top-1]);
31         }
32         else if(p==1)
33         {
34             if(top==0)continue;
35             s[top--]=0;    
36         }
37         else if(p==2)
38             printf("%d\n",s[top]);
39     }
40     return 0;
41 }