题解：P5661 [CSP-J2019] 公交换乘

WsW_ · 2024-12-25 13:46:59 · 题解

思路

按题意模拟。
用一个双端队列来存优惠票价和获得时间。
如果坐地铁，花费相应的钱数并且往双端队列里面塞一个优惠票。因为输入数据的时间递增，所以双端队列里优惠票的获得时间也是递增。
如果坐公交，先把过期的优惠票从双端队列里面删除，然后判断队首的票价是否能够使用。如果不能够，就把这张票塞到另外一个栈里面存着，并把这张票从双端队列中删除，重复这个过程。如果双端队列空了还没有能用的票，就得原价坐公交车，否则删除能用的票，免费坐公交车。最终还要把存在栈里面的票从队首塞回双端队列里。
因为票的有效期只有 45 分钟，所以双端队列里面最多只有 45 张票，时间复杂度为 O(45n)。

代码

#include<bits/stdc++.h>
using namespace std;
struct node{
    int t,val;
};
deque<node>q;
stack<node>s;
int n;
int opt,val,t;
int sum;

int main(){
    scanf("%d",&n);
    while(n--){
        scanf("%d%d%d",&opt,&val,&t);
        while(!q.empty()&&t-q.front().t>45)q.pop_front();
        if(opt){
            bool f=0;
            while(!q.empty()){
                if(q.front().val>=val){
                    f=1;
                    q.pop_front();
                    break;
                }
                s.push(q.front());
                q.pop_front();
            }
            while(!s.empty()){
                q.push_front(s.top());
                s.pop();
            }
            if(!f)sum+=val;
        }
        else{
            sum+=val;
            q.push_back({t,val});
        }
    }
    printf("%d",sum);
    return 0;
}