双端队列题解

思路如下：

1. 若乘坐地铁，总花费加上当前票价，将一张优惠票信息push_back进队列中（注意这里的时间顺序）；
2. 若乘坐公交，则先将所有过期票pop_front出去，再判断是否存在不低于当前票价的最早优惠票。如不存在，总花费加上当前票价；如存在，将那张票删除。

代码：

#include<queue>
#include<utility>
#include<iostream>
using namespace std;
int n,sum,cnt;
deque<pair<int,int> > q;//按时间顺序存储优惠票
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		bool op;
		int p,t;
		cin>>op>>p>>t;
		if(!op){//乘坐地铁
			q.push_back({p,t});
			sum+=p;
		}
		else{
			while(q.size() && q.front().second<t-45) q.pop_front();//删除过期票
			deque<pair<int,int> > q1;//临时存储未过期，但是不符合优惠要求的票
			while(q.size() && q.front().first<p){
				q1.push_back(q.front());//临时删除未过期，但是不符合优惠要求的票
				q.pop_front();
			}
			if(q.size()) q.pop_front();//如存在满足条件的票，将那张票删除
            else sum+=p;//如不存在，总花费加上当前票价
			while(q1.size()){
				q.push_front(q1.back());//将未过期，但是不符合优惠要求的票加回队列中
				q1.pop_back();
			}
		}
	}cout<<sum;//输出总花费
	return 0;
}