洛谷 1165日志分析

題目描述

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

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

輸入輸出格式

輸入格式：

?

包含N+1 行：

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

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

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

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

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

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

?

輸出格式：

?

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

?

輸入輸出樣例

輸入樣例#1：

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

輸出樣例#1：

2
4
4
1
0

說明

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

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

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

?

代碼

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
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;
}

這個代碼你會發現在提交時會tle.

為何？？

因為我們在每次進行查找時，都需要for循環一般，這樣會浪費掉很多時間。

那我們該如何做呢？？

下面我們來看一下正解！

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

是不是感覺這個代碼會wa，你看這把最大的放后面肯定不對！！

no

這個代碼是對的！

你看，我們每次輸入1的時候是把最后一個數進行刪除處理，而且他讓輸出序列中最的數，那小的數是否就沒有什么用了，所以，我們只需要把最大的數放在最后面就可以啦！！