检查站（单调递增队列）

spoiler posted @ 2011年4月09日 17:05 in 农大月赛解题报告 , 1465 阅读

题意就是有两个检查站，可以从第一个检查站开进车子，也会从后面一个检查站开出车子，但是每次只能动作一次，开出或者开进，你要求查询这两个检查站之间的最重车辆。

#include<iostream>
#include<stdio.h>
#include<list>
using namespace std;
 
struct node{
    int val,id;
};
 
int main(){
    int cas,x,sn,ans,t,times,en;
    char c[10];
    scanf("%d",&cas);
    list <node> que;
    node tempt ;
    en=sn=0;
    ans=0;
    times=0;
    while(cas--){
        scanf("%s",c);
                 //这样能节约很多时间！下次进行类似的字符输入
                 //用来判断的时候 切记 ！ 
             if(c=='Q'){
            if(que.empty())
                printf("0\n");
                        else
                printf("%d\n",que.front().val);
                }
        else if(c=='I'){
            scanf("%d",&x);
            ans++;
            tempt.val=x;
            tempt.id=ans;
            while(!que.empty()&&x>=que.back().val) 
                que.pop_back();
            que.push_back(tempt);
        }
        else{   
            times++;
            while(!que.empty()&&que.front().id<=times)
                que.erase(que.begin());
        }
    }
    return 0;
}