2019 公交换乘 · 方案二时间窗口优化

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 3/5 · 共 1328 字

45 分钟窗口内最多 45 张票，指针只增不减

2019
模拟

正文

// CSP-J 2019 复赛 T2 · 公交换乘（方案二 · 满分）
// 原题：https://oj.yecheng.tv/p/CSPJ2019B
//
// 方案二 · 时间窗口优化
// 关键观察：题目保证「不会有两次乘车记录出现在同一分钟」，
// 所以任意 45 分钟的窗口里最多只有 45 条记录，也就是最多 45 张票可能有效。
// 用一个下标 head 指向最早那张票，过期的票直接整体丢掉、永不回头；
// 每张公交最多只需比较 45 次，总复杂度 O(45n)，稳过 1e5。

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

struct Ticket {
    int price;
    int time;
    bool used;
};

int main() {
    freopen("transfer.in", "r", stdin);
    freopen("transfer.out", "w", stdout);

    int n;
    cin >> n;

    vector<Ticket> tickets;
    int head = 0;      // 最早一张还没过期、也没被丢掉的票
    int cost = 0;

    for (int i = 0; i < n; i++) {
        int kind, price, t;
        cin >> kind >> price >> t;
        if (kind == 0) {
            tickets.push_back({price, t, false});
            cost += price;
        } else {
            // 先把过期的票从窗口里划走，head 只增不减
            while (head < (int)tickets.size() && t - tickets[head].time > 45) head++;
            bool freeRide = false;
            for (int j = head; j < (int)tickets.size(); j++) {
                if (tickets[j].used) continue;
                if (tickets[j].price < price) continue;
                tickets[j].used = true;
                freeRide = true;
                break;
            }
            if (!freeRide) cost += price;
        }
    }

    cout << cost << "\n";
    return 0;
}

2019 公交换乘 · 方案二 时间窗口优化

正文

CSP-J 标程 · 复赛真题的其它内容

2019 公交换乘 · 方案二时间窗口优化