[CSP-J 2019] 公交换乘

知识点

模拟、队列、时间窗口

解题思路

用队列按获得时间维护优惠票，每张票记录票价、时间及是否使用。每次乘车先移除已经超过45分钟的队首优惠票。地铁记录直接付费并把新票加入队尾；公交记录从队首向后寻找第一张未使用且票价不少于本次公交票价的票，找到就标记使用，找不到才付费。时间是严格递增的整数，所以有效时间窗内最多只有46条记录，一次扫描的长度有常数上界。

正确性说明

队列始终按购票时间排列；弹出过期票后，队内每张未使用的票都仍在有效期内。由队首向后找到的第一张可用票，恰好是题目要求的获得最早的可用票。两种交通工具分别按规则付费或使用优惠票，故逐条处理所得总费用与题意一致。

易错点

时间差等于45时仍有效；公交不会生成新优惠票；已使用票不能再次使用；较早但票价不足的票不能直接删除，它可能用于后续较便宜的公交。总费用使用long long。

复杂度

时间O(46n)=O(n)，依据严格递增整数时间的题目约束；有效队列额外空间O(46)=O(1)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
struct Ticket{int price,time; bool used;};
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin>>n;
    deque<Ticket> q; long long ans=0;
    while(n--){
        int type,p,t; cin>>type>>p>>t;
        while(!q.empty() && t-q.front().time>45) q.pop_front();
        if(type==0){ans+=p; q.push_back({p,t,false});}
        else{
            bool freeRide=false;
            for(auto &x:q) if(!x.used && x.price>=p){
                x.used=true; freeRide=true; break;
            }
            if(!freeRide) ans+=p;
        }
    }
    cout<<ans<<'\n';
    return 0;
}