【CSP】CSP-J 2019真题 | 公交换乘 luogu-P5661 （适合GESP四级及以上考生练习）
CSP-J 2019真题- 公交换乘，模拟、队列考点，重点考察对于时间窗口内状态的维护以及阅读理解能力，适合GESP四级及以上考生练习，难度⭐⭐☆，洛谷难度等级普及−。
P5661 [CSP-J 2019] 公交换乘
题目要求
题目描述
著名旅游城市 B 市为了鼓励大家采用公共交通方式出行，推出了一种地铁换乘公交车的优惠方案：
- 在搭乘一次地铁后可以获得一张优惠票，有效期为 45 分钟，在有效期内可以消耗这张优惠票，免费搭乘一次票价不超过地铁票价的公交车。在有效期内指开始乘公交车的时间与开始乘地铁的时间之差小于等于 45 分钟，即：$t_{bus} - t_{subway} \leq 45$。
- 搭乘地铁获得的优惠票可以累积，即可以连续搭乘若干次地铁后再连续使用优惠票搭乘公交车。
- 搭乘公交车时，如果可以使用优惠票一定会使用优惠票；如果有多张优惠票满足条件，则优先消耗获得最早的优惠票。
现在你得到了小轩最近的公共交通出行记录，你能帮他算算他的花费吗?
输入格式
输入文件的第一行包含一个正整数 $n$，代表乘车记录的数量。
接下来的 $n$ 行，每行包含 3 个整数，相邻两数之间以一个空格分隔。第 $i$ 行的第 1 个整数代表第 $i$ 条记录乘坐的交通工具，0 代表地铁，1 代表公交车；第 2 个整数代表第 $i$ 条记录乘车的票价 $price_i$ ；第三个整数代表第 $i$ 条记录开始乘车的时间 $t_i$（距 0 时刻的分钟数）。
我们保证出行记录是按照开始乘车的时间顺序给出的，且不会有两次乘车记录出现在同一分钟。
输出格式
输出文件有一行，包含一个正整数，代表小轩出行的总花费。
输入输出样例 #1
输入 #1
1
2
3
4
5
6
7
6
0 10 3
1 5 46
0 12 50
1 3 96
0 5 110
1 6 135
输出 #1
1
36
输入输出样例 #2
输入 #2
1
2
3
4
5
6
7
6
0 5 1
0 20 16
0 7 23
1 18 31
1 4 38
1 7 68
输出 #2
1
32
说明/提示
【样例 1 说明】
第一条记录，在第 3 分钟花费 10 元乘坐地铁。
第二条记录，在第 46 分钟乘坐公交车，可以使用第一条记录中乘坐地铁获得的优惠票，因此没有花费。
第三条记录，在第 50 分钟花费 12 元乘坐地铁。
第四条记录，在第 96 分钟乘坐公交车，由于距离第三条记录中乘坐地铁已超过 45 分钟，所以优惠票已失效，花费 3 元乘坐公交车。
第五条记录，在第 110 分钟花费 5 元乘坐地铁。
第六条记录，在第 135 分钟乘坐公交车，由于此时手中只有第五条记录中乘坐地铁获得的优惠票有效，而本次公交车的票价为 6 元，高于第五条记录中地铁的票价 5 元，所以不能使用优惠票，花费 6 元乘坐公交车。
总共花费 36 元。
【样例 2 说明】
第一条记录，在第 1 分钟花费 5 元乘坐地铁。
第二条记录，在第 16 分钟花费 20 元乘坐地铁。
第三条记录，在第 23 分钟花费 7 元乘坐地铁。
第四条记录，在第 31 分钟乘坐公交车，此时只有第二条记录中乘坐的地铁票价高于本次公交车票价，所以使用第二条记录中乘坐地铁获得的优惠票。
第五条记录，在第 38 分钟乘坐公交车，此时第一条和第三条记录中乘坐地铁获得的优惠票都可以使用，使用获得最早的优惠票，即第一条记录中乘坐地铁获得的优惠票。
第六条记录，在第 68 分钟乘坐公交车，使用第三条记录中乘坐地铁获得的优惠票。
总共花费 32 元。
【数据规模与约定】
对于 $30\%$ 的数据，$n \leq 1000$，$t_i \leq 10^6$。
另有 $15\%$ 的数据，$t_i \leq 10^7$，所有 $price_i$ 相等。
另有 $15\%$ 的数据，$t_i \leq 10^9$，所有 $price_i$ 相等。
对于 $100\%$ 的数据，$n \leq 10^5$，$t_i \leq 10^9$，$1 \leq price_i \leq 1000$。
题目分析
本题是一道经典的模拟题，要求我们完全按照题目给出的规则，处理每一条乘车记录，并计算出总花费。
解题思路分析：
- 乘坐地铁的处理：
- 乘坐地铁时没有任何优惠，必须花费对应的金额。
- 每次乘坐地铁会产生一张新的优惠票，需要将这张优惠票的“可用金额（等于地铁原价）”和“获取时间”记录下来。
- 乘坐公交车的处理：
- 乘坐公交车时，我们需要在之前获得的、有效期限内且尚未被使用过的优惠票中，寻找一张价格大于等于当前公交车票价的票。
- 如果有多张满足条件的票，题目明确规定要优先使用最早获得的优惠票。如果寻找不到符合条件的票，就需要原价支付公交车费。
性能优化思路（滑动窗口 / 队列思想）：
由于数据量 $N \le 10^5$，如果我们每次乘坐公交车都从第一张优惠票开始查找，遇到连续全是公交车的情况，时间复杂度可能会退化到 $O(N^2)$，导致超时。 但是题目中有一个非常关键的限制条件：优惠票的有效期只有 45 分钟！ 这就意味着，对于当前时间 $t$，如果之前获取的优惠票的时间早于 $t - 45$，这就肯定是一张过期废票。 我们可以通过维护一个头尾指针（相当于队列）：每次乘地铁产生的优惠票都在数组尾部存入，而每次乘公交车需要检索优惠券之前，先把数组头部所有过期的优惠券直接跳过废弃。因为所有记录是按照时间升序排列的，一旦某张票过期，之后必定也永远过期，因此“头部淘汰”的操作具有单调性。这种优化也叫“滑动窗口”，能使查询的时间复杂度被控制在常数级（比如最多查找45条记录），总体时间复杂度能大幅降低，以保证不超时。
示例代码
结构体+数组模拟队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
// 定义优惠券结构体
struct Ticket {
int price; // 地铁票价（可抵扣最大金额）
int time; // 乘车时间
bool used; // 是否已被使用
};
Ticket tickets[100005]; // 存储所有获得的优惠票
int head = 0, tail = 0; // 模拟滑动窗口（队列）的头尾指针
int main() {
int n;
std::cin >> n;
long long total_cost = 0; // 记录总花费，建议使用 long long 防爆 int
for (int i = 0; i < n; i++) {
int type, price, time;
std::cin >> type >> price >> time;
if (type == 0) {
// 类型 0：乘坐地铁
// 必然要花钱，花费累加
total_cost += price;
// 获得一张新优惠票，放入数组尾部并扩展 tail
tickets[tail].price = price;
tickets[tail].time = time;
tickets[tail].used = false;
tail++;
} else {
// 类型 1：乘坐公交车
// 步骤 1：清理队头已经过期的旧优惠票，缩小查找范围
// 如果 head 指向的票据已经越过了 45 分钟的有效期，直接淘汰不看
while (head < tail && time - tickets[head].time > 45) {
head++;
}
// 步骤 2：从队头开始（此时剩下的都是未过期的）向后遍历，找到恰好满足条件的票并使用
bool found = false;
for (int j = head; j < tail; j++) {
// 如果当前优惠票未被使用，且抵用额度大于等于公交车票价
if (!tickets[j].used && tickets[j].price >= price) {
tickets[j].used = true; // 标记为已使用
found = true; // 标记找到了可用优惠票
break; // 题目要求优先使用最早获得的，故找到最早的一张立即退出
}
}
// 步骤 3：如果刚才没找到符合条件的优惠券，那么只能原价乘公交车
if (!found) {
total_cost += price;
}
}
}
// 输出最终开销数字
std::cout << total_cost << std::endl;
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
"luogu-"系列题目可在洛谷题库进行在线评测。
"bcqm-"系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
