P5661 [CSP-J2019] 公交换乘

考都考了，那就发一篇吧

（我会把pj前三题的题解做个整合版发在lg博客里，敬请期待！）

这道题基本在意料之中，和龙虎斗类型相似的枚举模拟题，虽然算法简单但是小坑无数

Part 1

看到这题第一反应是“这么简单的一题啊”

迅速开编。

直接模拟即可。开变量记录上一张票的截止时间，逢公交判断即可。

发现可以边读入边处理，节省空间

5min after...

诶肿么样例输错了？！[蒟蒻在线懵逼]

好再来康康...

诶！

由于此时手中只有第五条记录中乘坐地铁获得的优惠票有效，而本次公交车的票价为 6 元，高于第五条记录中地铁的票价 5 元，所以不能使用优惠票

woc...还有这个要求！

Part 2

那好办，直接再开个变量记录上一次地铁票价，加一个判断就成。

3min后...

好，我们来看看第一个样例...啊！输对了！[蒟蒻的笑容]

然后突然扫到一句话：

如果有多张优惠票满足条件，则优先消耗获得最早的优惠票。

woc!!还会有多张优惠票?!那...直接开一个变量记录的方法直接推翻。

[来自蒟蒻的尴尬而又不是礼貌的微笑]

Part 3

于是决定开结构体数组存储票价信息。

然后又发现如果每次做公交时都从头遍历一遍所有票会T，所以又愣住了

然后突然想起 P2058 [NOIp2016] 海港的一种“滑动窗口”算法，惊讶的发现可以用于这道题。

于是算法就是记录下每次可用票的区间[x,y]的x和y，于是循环可以从x至y，就不会T了。

可用票的区间定义为：全体“未过期”的票包含在此区间内。

有那么一瞬间想到了（在一位奆佬博客里看到过的）优先队列，但是忘了肿么写了。所以就采用了结构体数组加“滑动窗口”。蒟蒻太弱了居然没有意识到这就是优先队列

于是代码就有了。15:30过了大样例，就默认锕了。

#include 
 
using namespace std;
const int MAXN = 100005;
struct Ticket {
    int price, time, used;
} q[MAXN];
int head, tail, n, cost;
 
int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int op, price, time;
        cin >> op >> price >> time;
        if (op == 0) {
            cost += price;
            q[tail].time = time + 45;
            q[tail++].price = price;
        } else {
            while (head < tail && q[head].time < time) {
                head++;
            }
            bool found = false;
            for (int j = head; j < tail; ++j) {
           
                if (q[j].price >= price && q[j].used == 0) {
             
                    found = true;
                    q[j].used = 1;
                    break;
                }
            }
      
            if (!found) cost += price;
        }
    }
    cout << cost << endl;
    return 0;
}