洛谷p5661这道题（CSP-J 2019 T2 公交换乘）是一道非常经典的模拟题目。

虽然题目描述很长，但核心逻辑其实就在模拟“优惠票”的产生、存储、过期和使用过程。只要选对了数据结构，代码并不复杂。

核心思路分析

1. 数据结构选择：

   • 由于优惠票是先获得的可能先过期，但使用时又是优先使用“最早获得的有效票”，这看起来像一个队列。
   • 我们需要一个容器来存储还未过期的地铁优惠票。
   • 因为 $N \le 10^5$，我们不能每次坐公交都把历史记录从头扫一遍（那样是 $O(N^2)$，会超时）。
   • 关键点：优惠票有效期只有 45 分钟。题目保证记录是按时间顺序给出的。这意味着，对于任何一次公交出行，只需要检查最近 45 分钟内的地铁记录。
   • 由于题目保证“不会有两次乘车记录出现在同一分钟”，所以 45 分钟内的地铁记录最多只有 45 条。这是一个非常小的常数。

2. 模拟逻辑：

   • 遇到地铁 (0)：
     • 必须花钱，总花费 += 票价。
     • 获得一张优惠票，存入数组/队列。记录属性：{价格, 时间, 是否已使用}。
   • 遇到公交 (1)：
     • 我们需要在存储的优惠票中寻找一张符合条件的票。
     • 筛选顺序：从最早的记录开始找（因为题目要求“优先消耗获得最早的优惠票”）。
     • 过期处理：如果最早的记录时间差超过了 45 分钟，说明这张票彻底作废了（因为时间是递增的，现在过期的以后更过期），我们可以直接移动“队头指针”，以后不再检查它。
     • 有效性检查：
       1. 时间差 $\le 45$ 分钟。
       2. 没有被使用过 (used == false)。
       3. 地铁票价 $\ge$ 公交票价。
     • 结果：
       • 找到符合条件的：把这张优惠票标记为“已使用”，本次公交免费。
       • 找了一圈没找到：必须花钱，总花费 += 票价。

3. 时间复杂度：

   • 外层循环遍历 $N$ 条记录。
   • 内层循环在坐公交时查找优惠票。虽然看起来是两层循环，但由于我们维护了一个“滑动窗口”（只看 45 分钟内），内层循环次数极少（最多约 45 次）。
   • 总复杂度接近 $O(N)$，对于 $10^5$ 的数据量非常安全。

代码实现

建议使用 struct 结构体数组来模拟这个队列，配合 head（头指针）和 tail（尾指针）来管理。

#include <iostream>
#include <vector>
using namespace std;

// 定义优惠票结构体
struct Ticket {
    int price;  // 票价
    int time;   // 时间
    bool used;  // 是否已使用
};

// 开一个足够大的数组来充当队列
// 数据范围 N <= 100000
Ticket q[100005]; 
int head = 0; // 队列头指针（指向最早的可能有效的票）
int tail = 0; // 队列尾指针（指向下一个空的存储位置）

int main() {
    // 优化输入输出效率
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    long long ans = 0; // 总花费，虽然题目数据可能int够，但开long long是好习惯

    for (int i = 0; i < n; i++) {
        int type, price, time;
        cin >> type >> price >> time;

        if (type == 0) {
            // === 坐地铁 ===
            // 1. 必须花钱
            ans += price;
            // 2. 获得优惠票，存入队列尾部
            q[tail].price = price;
            q[tail].time = time;
            q[tail].used = false;
            tail++; // 尾指针后移
        } else {
            // === 坐公交 ===
            bool found = false; // 标记是否找到了可用优惠票

            // 遍历队列，寻找可用优惠票
            // 从 head 开始找，因为要优先用最早的
            for (int j = head; j < tail; j++) {
                // 1. 检查是否过期
                if (time - q[j].time > 45) {
                    // 如果这张票已经过期了，那么它以及它前面的票以后都不可能用到了
                    // 直接把 head 指针移到 j+1，相当于把前面的废票都扔掉
                    // 这一步是优化的关键
                    head = j + 1; 
                    continue;
                }

                // 2. 检查是否可用（未被使用 且 价格足够）
                if (!q[j].used && q[j].price >= price) {
                    q[j].used = true; // 标记为已使用
                    found = true;     // 找到了
                    break;            // 找到一张就够了，退出循环
                }
            }

            // 如果遍历完滑动窗口里的票都没找到合适的
            if (!found) {
                ans += price;
            }
        }
    }

    cout << ans << endl;

    return 0;
}

易错点提示

1. Head 指针的移动： 在内层循环中，如果发现 time - q[j].time > 45，我们执行了 head = j + 1。这是基于时间是递增的特性。如果你现在的票都过期了，下一个公交车来的时候时间更晚，这张票肯定也过期了，所以可以直接扔掉（也就是 head 前移），避免下次重复检查。

2. Used 标记： 千万别忘了 !q[j].used 这个判断。有些票虽然没过期、价格也够，但如果之前坐别的公交车用过了，就不能再用了。

3. Break 的时机： 一旦找到一张合适的票，标记使用后必须立刻 break。因为题目要求“如果可以使用优惠票一定会使用优惠票”，而且只消耗一张。如果不 break，可能会继续往后找。

加油！这道题考察的就是把生活中的规则转化为代码逻辑的能力。

C++ :

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
//优惠券
struct Ticket
{
    int time, price;
    bool used;
} tk[N];

int main()
{
    scanf("%d", &n); // 表示总记录数量

    int res = 0; // 总花费
    for (int i = 0, l = 0, r = 0; i < n; i++)
    {
        int type, price, time;
        scanf("%d%d%d", &type, &price, &time);
        if (type == 0)
        {
            res += price;
            tk[r++] = {time, price};
        }
        else
        {
            while (l < r && time - tk[l].time > 45) l++; //弹出不在窗口内的所有优惠券

            bool success = false;
            for (int i = l; i < r; i++)
                if (tk[i].used == false && tk[i].price >= price)
                {
                    tk[i].used = true; //表示优惠券被用过了，防止重复使用
                    success = true;
                    break;
                }
            if (!success)
                res += price;
        }
    }

    printf("%d\n", res);

    return 0;
}