一、题目重现

题目描述

著名旅游城市 B 市为了鼓励大家采用公共交通方式出行，推出了一种地铁换乘公交车的优惠方案：

1. 在搭乘一次地铁后可以获得一张优惠票，有效期为 45 分钟，在有效期内可以消耗这张优惠票，免费搭乘一次票价不超过地铁票价的公交车。在有效期内指开始乘公交车的时间与开始乘地铁的时间之差小于等于 45 分钟，即 t(bus) − t(subway) ≤ 45。
2. 搭乘地铁获得的优惠票可以累积，即可以连续搭乘若干次地铁后再连续使用优惠票搭乘公交车。
3. 搭乘公交车时，如果可以使用优惠票一定会使用优惠票；如果有多张优惠票满足条件，则优先消耗获得最早的优惠票。

现在你得到了小轩最近的公共交通出行记录，你能帮他算算他的花费吗？

输入格式

输入文件的第一行包含一个正整数 n，代表乘车记录的数量。

接下来的 n 行，每行包含 3 个整数，相邻两数之间以一个空格分隔。第 i 行的第 1 个整数代表第 i 条记录乘坐的交通工具，0 代表地铁，1 代表公交车；第 2 个整数代表第 i 条记录乘车的票价 price_i；第三个整数代表第 i 条记录开始乘车的时间 t_i（距 0 时刻的分钟数）。

我们保证出行记录是按照开始乘车的时间顺序给出的，且不会有两次乘车记录出现在同一分钟。

输出格式

输出文件有一行，包含一个正整数，代表小轩出行的总花费。

输入输出样例

样例 1

6
0 10 3
1 5 46
0 12 50
1 3 96
0 5 110
1 6 135

36

样例 2

6
0 5 1
0 20 16
0 7 23
1 18 31
1 4 38
1 7 68

32

样例 1 说明

• 第 3 分钟花费 10 元坐地铁；
• 第 46 分钟坐公交，可以用上一条的优惠票，免费；
• 第 50 分钟花费 12 元坐地铁；
• 第 96 分钟坐公交，距第 50 分钟已超过 45 分钟，优惠票失效，付 3 元；
• 第 110 分钟花费 5 元坐地铁；
• 第 135 分钟坐公交，此时唯一有效的优惠票来自第 110 分钟的地铁（票价 5 元），而本次公交票价 6 元高于它，用不了，付 6 元。

总计 10 + 12 + 3 + 5 + 6 = 36 元。

样例 2 说明

三条地铁（第 1、16、23 分钟）产生三张券，第 31 分钟用掉第 16 分钟那张（只有它票价 20 ≥ 18），第 38 分钟可用的有第 1、23 分钟两张，按规则用最早获得的第 1 分钟那张，第 68 分钟用掉第 23 分钟那张。总计 5 + 20 + 7 = 32 元。

数据规模与约定

二、题意提炼

把三条规则翻译成程序语言：

注意最后一条：这不是”能省则省”的优化问题，而是题目规定必须用票，且规定了用哪张。所以不需要纠结贪心策略，照着规则模拟即可。

三、核心思路

一句话：用一个队列维护 45 分钟滑动窗口内的所有优惠票。

• 队列里只放地铁票，因为只有坐地铁才会产生优惠票；
• 队列按获得时间递增，队头就是”最早获得的券”，天然满足”优先消耗最早”的规则；
• 每遇到一趟公交车，做三件事：
  1. 清理过期：把队头所有已过期的券弹掉；
  2. 找可用券：从队头往后找第一张”票价够用”且”还没用过”的券；
  3. 结算：找到就免单并标记该券已用；找不到就老老实实付钱。

为什么找券时要”搬出去再搬回来”？

deque 只能访问两端，而可用的券可能埋在中段（队头几张票价太低，用不上）。同时，队列的时间序是后续过期判断的依据，不能破坏。

于是借助一个辅助容器 q1：把途中”不合格”的券依次搬进去，命中后再按原顺序搬回来。

q1 只用了 push_front / front / pop_front 三个操作，语义上完全等价于一个栈（后进先出）——所以搬回去的顺序正好是搬出来的逆序，复原后 q 与扫描前一模一样。

扫描前:   q = [A][B][C][D]        front 在左
扫描中:   A、B 不合格 → 搬进 q1；C 命中 → 标记 used 并 break
          q  = [C][D]             q1 = [B]        ← 栈顶
                                       [A]
还原后:   q = [A][B][C][D]        与扫描前完全一致，只是 C 带了 used 标记

四、参考代码（AC）

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

const int N = 1e5 + 5;

struct node{
    int time, val, used;   // time: 优惠票失效时刻  val: 地铁票价  used: 是否已用
};

deque<node> q, q1;         // q: 优惠票池  q1: 找券时的临时栈
int n, ans;

int main(){
    cin >> n;
    for(int i = 0 ; i < n ; i ++){
        int x, p, t;
        cin >> x >> p >> t;
        if(x == 0){                      // 地铁：付费，同时获得一张优惠票
            ans += p;
            q.push_back({t + 45, p, 0});
        }else{                           // 公交：尝试用票
            while(q.size() && q.front().time < t){   // ① 清理过期券
                q.pop_front();
            }
            bool flag = 1;                           // 悲观初始化：先假定要付钱
            while (q.size()) {                       // ② 从队头找第一张可用券
                if(q.front().val >= p && q.front().used == 0){
                    flag = 0;
                    q.front().used = 1;              // 先标记，再退出
                    break;
                }
                q1.push_front(q.front());            // 不合格 → 搬进临时栈
                q.pop_front();
            }
            while(q1.size()){                        // ③ 原样搬回来
                q.push_front(q1.front());
                q1.pop_front();
            }
            if(flag){                                // ④ 没找到就付钱
                ans += p;
            }
        }
    }
    cout << ans;
    return 0;
}

五、代码逐行解析

数据结构

struct node{
    int time, val, used;
};
deque<node> q, q1;

• time 存的不是乘车时刻，而是失效时刻 t + 45，这是理解整段代码的关键；
• val 是产生这张券的地铁票价；
• used 标记这张券是否已经被消耗；
• q 是名义上的优惠票池，q1 只在找券时临时借用。

分支一：坐地铁（x == 0）

ans += p;
q.push_back({t + 45, p, 0});

地铁没有免单的可能，直接计费；同时产生一张有效期到 t + 45 的优惠票，从队尾加入票池。因为输入按时间递增，队尾加入天然保证了整个队列按时间有序。

分支二：坐公交（x == 1）

Step 1｜先扫掉过期券

while(q.size() && q.front().time < t){
    q.pop_front();
}

队头是最早获得的券，如果它的失效时刻都小于当前时刻 t，说明它已超出 45 分钟窗口，直接丢弃。

边界细节：time 记录的是 t_地铁 + 45，判断用 < 而不是 <=，所以”正好第 45 分钟”仍然有效（t - t_地铁 = 45），符合题意。由于队列按时间有序，过期的一定堆在队头，一路 pop_front 即可，不需要扫描全队。

Step 2｜找券：q1 是一个临时栈（核心）

bool flag = 1;                       // 1 = 没找到券，默认要付钱
while (q.size()) {
    if(q.front().val >= p && q.front().used == 0){
        flag = 0;
        q.front().used = 1;          // 先标记，再 break
        break;
    }
    q1.push_front(q.front());        // 用不了 → 搬到 q1 暂存
    q.pop_front();
}

两个条件必须同时满足：

两个关键点：

1. 命中时这张券没有 pop 出来，它继续留在 q 里占位，只是打了 used = 1 的标记。以后再有公交扫到它，会被 used == 0 挡掉。这样做的好处是省去了”从 deque 中间删除元素”的操作。
2. 不合格的券不能直接扔。它们对后面某趟更便宜的公交可能仍然有效，而且队头”最早”这个性质也不能破坏，所以先搬进 q1 暂存。

Step 3｜把 q 原样还原

while(q1.size()){
    q.push_front(q1.front());
    q1.pop_front();
}

q1 是个栈，栈顶是最晚被搬出去的那张券，push_front 回 q 的头部，正好站回它原来的位置。一路弹完，q 恢复成扫描前的样子，顺序分毫不差。

顺带地，这个循环也把 q1 清空了——所以 q1 是全局变量也没关系，下次公交进来时它是干净的，可以放心复用。

打个比方：这就像在书里找某一页。deque 只能看两头，所以得把前面的书页抽出来码在旁边，找到后按原顺序插回去。

Step 4｜兜底付钱

if(flag){
    ans += p;
}

flag 还是 1，说明一张券都没找到，这趟公交正常计费。

六、复杂度分析

时间

设队列长度为 k，每趟公交最坏扫描 k 次，总复杂度 O(n·k)。

这道题的关键保证是：不会有两次乘车记录出现在同一分钟。 即所有 t_i 严格递增（整数分钟）。那么 45 分钟窗口 [t − 45, t] 内最多只能容纳 45 + 1 = 46 条记录，因此：

队列长度 k ≤ 46，实际复杂度 O(45n) ≈ O(n)。

空间

队列最多同时存在 46 张券，空间 O(1) 量级。

实测

注意：这套写法能过的前提就是”同一分钟不重复”这条保证。如果数据允许 10 万条记录挤在同一个 45 分钟窗口内，队列长度会退化到 O(n)，整体变成 O(n²)，就会被卡掉。

七、易错点清单

1. time 存的是 t + 45（失效时刻），不是乘车时刻。 判断过期写 q.front().time < t，等价于 t - t_地铁 > 45。写成 <= 会把”正好第 45 分钟”误判为过期。
2. val >= p 别写反。 val 是地铁票价，p 是公交票价，题意是”公交票价不超过地铁票价”。
3. 命中后要先标记 used = 1 再 break，而且这张券不能弹出队列——它还要留在原位占位，只是以后会被 used 挡掉。
4. 不满足条件的券不能直接丢弃。 它们对后续某趟更便宜的公交仍可能有效。
5. q1 用完必须清空。 它是全局变量，下次找券还要复用；while(q1.size()) 这个还原循环正好把它清干净。
6. 答案范围：最大约 10^5 × 1000 = 10^8，int 够用；但写 long long 是更稳的习惯。
7. 多张券可用时，必须用”最早获得”的那张。 因为队列按时间有序，从队头往后找第一张可用的即可，不要自作主张挑票价最接近的那张。

八、另一种等价写法

利用”窗口内最多 46 条记录”这一结论，也可以完全不用队列，直接开数组、每次只回看最近 50 条记录：

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

int n, ans;
int op[100005], pri[100005], t[100005];
bool used[100005];

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> op[i] >> pri[i] >> t[i];
        if(op[i] == 0){                 // 地铁
            ans += pri[i];
            continue;
        }
        bool flag = 0;                  // 是否成功用券
        for(int j = max(1, i - 50); j < i; j++){
            if(op[j] == 0 && !used[j] && t[i] - t[j] <= 45 && pri[j] >= pri[i]){
                used[j] = 1;
                flag = 1;
                break;                  // 找到时间最早的一张就停
            }
        }
        if(!flag) ans += pri[i];
    }
    cout << ans;
    return 0;
}

两种写法本质相同：都是从”最早的券”开始往后找第一张能用的。第一种用队列显式维护窗口，更能体现”时间窗口 + 先进先出”的模型；第二种借用了窗口大小的上界做常数回看，写起来更短。

九、考点总结

一句话总结：q 是 45 分钟滑动窗口里的优惠票队列，q1 是找券时的临时栈；找到能用且未使用的券就免单，找不到就付钱。

本文题面整理自 CCF 官方公布的 CSP-J 2019 试题，题目版权归中国计算机学会所有。解析与代码由椰程信奥整理撰写，答案仅供参考，最终以 CCF 官方公布为准。