检查站(单调递增队列)

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

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

#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;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter