[CSP-J 2019]T2公交换乘题解

题意解析:

本题我认为是一个数据结构+模拟的题目，主要考查了队列的用法和FIFO的概念
$\newline$
本题为输入$n$个行程，并且保证$t_i$ > $t_{i-1}$，也就是本次行程一定晚于上一次行程
每次行程分为使用地铁和公交车两种方式
乘坐地铁时，花费$price_i$元，并获得一张免费范围为$price_i$，使用期限为$45mins$以下的券
乘坐公交车时，如果有在使用期限内的券，并且花费在免费范围内就必须使用免费特权，如果有多个满足的券，使用最早的券，如果没有满足的券就花费$price_i$乘坐公交车
最后求这份行程的花费

思路讲解:

维护一个队列，让它保持从队头至队尾每个优惠券的使用时间从小到大。
当遇到乘坐公交车时，先清除掉过期的优惠券，因为期限从小到大，所以当遍历到一个券在使用期限内即可停止清空过期券。
在清空完过期券后，为了保持顺序，使用一个临时的$vector$动态数组记录除了被用掉的券以外的券的相对顺序，最后将除了用掉的券，其他的重新放回队列。
$------------到这里，先写一下吧，实在不会再来看代码-----------$

#include <bits/stdc++.h>
using namespace std;
struct ticket {
    int getT; // 其实在我写的时候，我想这好像也可以换成过期时间，不过没有实践
    int free_price; // 免费票价权力的范围
};queue<ticket> q; // 维护的队列
int n, sum;
signed main() {
    cin >> n;
    for (int i = 1;i <= n;i++) {
        int bors, price, t;
        cin >> bors >> price >> t;
        if (bors == 0) { // 当乘坐的是地铁时，将券放入队列，增加花费
            q.push({t, price});
            sum += price;
        }
        else { // 乘坐公交车时,
            bool flag = true; // 判断有没有使用免费权力，true为没有，false为有(这里是为了偷懒QAQ)
            while (q.size() && t - q.front().getT > 45)q.pop(); // 清空过期券
            vector<ticket>tmp; // 创建保持相对时间顺序的记录数组
            while(q.size()){ // q.size()在此处等价于!q.empty()
                ticket tkt = q.front();q.pop(); 
                if (flag && price <= tkt.free_price){ // 如果没有被消耗过券并且条件允许
                    flag = false; // 如果条件允许，就消耗掉这张券并且将权力改为有
                }else tmp.push_back(tkt); // 如果这张券条件不允许或者已经消耗过券，将它放入记录数组
            }
            for (auto x : tmp)q.push(x); // 最后将记录数组里的数据重新放入队列
            if (flag)sum += price;	 // 如果没有行使免费权力，花费price元
        }
    }
    cout << sum;
    return 0;
}