[CSP-J 2019] 公交换乘

GitHub跳转原题关系图返回列表

用全局时间队列清理过期优惠票，再按票价分桶寻找最早可用且票价足够的地铁券。

OJ: luogu

题目 ID: P5661

难度:普及/提高-

标签:模拟队列cspj

日期: 2026-06-18 14:23

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

每次乘地铁都能得到一张优惠票：

  • 有效期 45 分钟；
  • 只能免费坐一次公交；
  • 只能用于票价不超过这次地铁票价的公交。

处理公交时：

  • 如果有可用优惠票，就一定要使用；
  • 如果有多张可用票，要优先使用获得时间最早的那张。

现在按时间顺序给出所有出行记录，要求求出总花费。

思路

先看最直接的做法：把每次地铁得到的优惠票都存起来。

遇到公交时，从最早的优惠票开始往后扫，找第一张满足：

  1. 还没被用过；
  2. 没过期；
  3. 地铁票价不少于当前公交票价。

找到就把它用掉，否则自己付公交钱。

这个写法最好理解：

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;
}

但它在每次公交时都可能扫描很多历史地铁票，最坏会变成平方级。

这题真正有用的观察有两个：

  1. 时间是递增输入的，所以过期券一定能按顺序从前面整段删掉。
  2. price_i <= 1000，票价范围很小，可以直接按票价开桶。

于是我们维护：

  • 一个全局时间队列，专门负责清理过期优惠票；
  • 1000 个价格桶队列，bucket[p] 里存票价恰好为 p 的地铁券编号；
  • 一个 removed 标记，表示某张券是否已经过期或被使用。

处理公交票价为 x 的记录时：

  • 只需看所有 p >= x 的桶；
  • 每个桶的队头都是这个票价下最早可用的券；
  • 再从这些候选里选编号最小的那张，就等价于“选获得时间最早的那张券”。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100000 + 5;
const int maxp = 1000 + 5;

struct Ticket {
    int price;
    int time;
    int id;
};

int n;
int typ[maxn], price[maxn], tim[maxn];
long long ans;
queue<Ticket> all_tickets;
queue<int> bucket[maxp];
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];

        while (!all_tickets.empty() && all_tickets.front().time + 45 < tim[i]) {
            removed_ticket[all_tickets.front().id] = true;
            all_tickets.pop();
        }

        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;

        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;
}

复杂度

  • 时间复杂度：O(n∗1000)O(n * 1000)
  • 空间复杂度：O(n)O(n)

总结

这题难点不在模拟规则本身，而在把规则拆成两个容易维护的维度：

  • 时间是否过期；
  • 票价是否足够。

一旦利用了“票价最多只有 1000”这个条件，就能用非常朴素、但足够稳的分桶做法通过。