dq题解

这道题用了双端队列（deque) 如果用vector应该也可以实现（？
我们知道坐地铁时必须付钱所以直接让ans加上，而且每做一次地铁会送一个优惠票所以将他存进双端队列的末尾
如果坐的是公交就从队首开始判断双端队列中的元素也就是优惠票是否过期了（超过45分钟）如果过期了就将其弹出
删除完过期票后就遍历判断双端队列中的优惠票能否抵消此次的公交费用，能就将队列中元素删除（erase），不能就原价加进ans

#include<bits/stdc++.h>
using namespace std;
struct Node{
long long id;
long long price;
long long time;
}q[1000100];
int main(){
    long long n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>q[i].id>>q[i].price>>q[i].time;
    }
    deque<Node> dq;
    long long ans=0;
    for(int i=1;i<=n;i++){
        if(q[i].id==0){
            ans+=q[i].price;
            dq.push_back(q[i]);
        }else{
            while(dq.size()){
                Node q2=dq.front();
                if(q[i].time-q2.time>45){
                    dq.pop_front();
                }else break;
            }
            bool f=false;
            for(long long j=0;j<dq.size();j++){
                if(q[i].price<=dq[j].price){
                    f=true;
                    dq.erase(dq.begin()+j);
                    break;
                }
            }
            if(f==false){
                ans+=q[i].price;
            }
        }
    }
    cout<<ans;
}