用全局时间队列清理过期优惠票，再按票价分桶寻找最早可用且票价足够的地铁券。
OJ: luogu
题目 ID: P5661
难度:普及-
标签:模拟队列cspj
创建: 2026-06-18 14:23
更新: 2026-10-25 19:18
题意
每次乘地铁都能得到一张优惠票：
- 有效期 45 分钟；
- 只能免费坐一次公交；
- 只能用于票价不超过这次地铁票价的公交。
处理公交时：
- 如果有可用优惠票，就一定要使用；
- 如果有多张可用票，要优先使用获得时间最早的那张。
现在按时间顺序给出所有出行记录，要求求出总花费。
思路
先看最直接的做法：把每次地铁得到的优惠票都存起来。
遇到公交时，从最早的优惠票开始往后扫，找第一张满足：
- 还没被用过；
- 没过期；
- 地铁票价不少于当前公交票价。
找到就把它用掉，否则自己付公交钱。
这个写法最好理解：
cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000 + 5;
struct Ticket {
int price;
int time;
bool used;
};
int n;
int typ, price, tim;
long long ans;
vector<Ticket> tickets;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> typ >> price >> tim;
if (typ == 0) {
ans += price;
tickets.push_back({price, tim, false});
continue;
}
int choose = -1;
for (int j = 0; j < (int) tickets.size(); j++) {
if (tickets[j].used) {
continue;
}
if (tim - tickets[j].time > 45) {
continue;
}
if (tickets[j].price < price) {
continue;
}
choose = j;
break;
}
if (choose == -1) {
ans += price;
} else {
tickets[choose].used = true;
}
}
cout << ans << '\n';
return 0;
}但它在每次公交时都可能扫描很多历史地铁票，最坏会变成平方级。
这题真正有用的观察有两个：
- 时间是递增输入的，所以过期券一定能按顺序从前面整段删掉。
price_i <= 1000，票价范围很小，可以直接按票价开桶。
于是我们维护：
- 一个全局时间队列，专门负责清理过期优惠票；
1000个价格桶队列，bucket[p]里存票价恰好为p的地铁券编号；- 一个
removed标记，表示某张券是否已经过期或被使用。
处理公交票价为 x 的记录时：
- 只需看所有
p >= x的桶； - 每个桶的队头都是这个票价下最早可用的券；
- 再从这些候选里选编号最小的那张，就等价于“选获得时间最早的那张券”。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000 + 5; // 最大记录数 n <= 1e5
const int maxp = 1000 + 5; // 票价上限 price <= 1000，按票价分桶
// 一张地铁优惠票的完整信息
struct Ticket {
int price; // 地铁票价（可抵扣的额度）
int time; // 乘地铁的时间
int id; // 记录编号（同时是获得顺序，越小越早）
};
int n;
int typ[maxn], price[maxn], tim[maxn]; // 第 i 条记录：类型(0地铁/1公交)、票价、时间
long long ans; // 总花费
// all_tickets：所有"未过期且未被使用"的地铁票，按获得时间(记录编号)递增
// 用它来按时间顺序丢弃超过 45 分钟的过期票
queue<Ticket> all_tickets;
// bucket[p]：票价为 p 的地铁票的记录编号，同桶内编号递增
// 因为"若有多张可用票优先用最早的"，所以每个桶只需看队首
queue<int> bucket[maxp];
// removed_ticket[i]：第 i 条记录（地铁票）是否已失效(过期/已使用)
// 采用"惰性删除"：不在队列中间真正删除，只在出队时跳过
bool removed_ticket[maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> typ[i] >> price[i] >> tim[i];
// 记录按时间递增给出，因此只需要从队首弹出过期的票
// 条件：t_bus - t_subway > 45 即失效
while (!all_tickets.empty() && all_tickets.front().time + 45 < tim[i]) {
removed_ticket[all_tickets.front().id] = true;
all_tickets.pop();
}
// 乘地铁：必须花钱，同时获得一张有效期为 45 分钟的优惠票
if (typ[i] == 0) {
ans += price[i];
all_tickets.push({price[i], tim[i], i});
bucket[price[i]].push(i);
continue;
}
// 乘公交：在票价 >= 本次票价的桶里找最早获得的那张票
int choose_id = -1; // 选中的票的记录编号
int choose_price = -1; // 选中的票的票价（即所在桶）
// 票价只需枚举到 1000；每个桶先惰性弹出已失效的票，再看队首
for (int p = price[i]; p <= 1000; p++) {
while (!bucket[p].empty() && removed_ticket[bucket[p].front()]) {
bucket[p].pop();
}
if (!bucket[p].empty()) {
int id = bucket[p].front();
// 多个桶都有票时，取记录编号最小的（获得最早的）
if (choose_id == -1 || id < choose_id) {
choose_id = id;
choose_price = p;
}
}
}
if (choose_id == -1) {
// 没有可用优惠票，只能全价乘车
ans += price[i];
} else {
// 用掉这张票：标记失效，并从对应桶中弹出
removed_ticket[choose_id] = true;
bucket[choose_price].pop();
}
}
cout << ans << '\n';
return 0;
}复杂度
- 时间复杂度：
- 空间复杂度：
总结
这题难点不在模拟规则本身，而在把规则拆成两个容易维护的维度：
- 时间是否过期；
- 票价是否足够。
一旦利用了“票价最多只有 1000”这个条件，就能用非常朴素、但足够稳的分桶做法通过。