c++|P5661 [CSP-J2019] 公交换乘信息技术|算法|c++|题解

考都考了，那就发一篇吧
（我会把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; }

【c++|P5661 [CSP-J2019] 公交换乘】