P4836 公交换乘（提高）

解题思路

第一步，看懂优惠规则。 坐地铁需要花钱，但坐完地铁会得到一张优惠票，这张票45分钟内有效。之后坐公交车时，只要存在一张"没过期、且这张票对应的地铁票价不低于这次公交票价"的优惠票，就必须使用它免费乘车；如果有好几张都能用，就使用获得最早的那张。如果找不到能用的票，公交车就得花钱买。题目要我们算出总共花了多少钱。

第二步，用队列保存还没用掉的优惠票。 优惠票是按获得时间先后排队的，最早获得的票自然排在最前面，正好符合"优先用最早获得"的规则。我们用三个数组模拟这个队列：tp 存每张票对应的地铁票价，tt 存这张票获得的时间，used 标记这张票是否已经用过；head 和 tail 分别是队列的头尾指针。

第三步，一条一条处理出行记录。 如果是坐地铁：把票价加进总花费，并把这张新票放进队列尾部。如果是坐公交车：先把队列头部"已经超过45分钟"的过期票清掉（因为记录按时间排序，过期票一定集中在队头）；然后从队头开始往后找第一张"没用过、且票价不低于公交票价"的票，找到了就标记用过、这趟免费；找不到就乖乖付钱。

第四步，为什么从队头找就一定是"最早获得"？ 因为票按时间先后依次放进队列，从头开始扫，扫到的第一张可用票自然就是获得时间最早的，完全符合题目"有多张优惠票时优先消耗最早获得"的要求。注意车票过期后要先从队头清除，避免拿过期的票去坐车。

第五步，用样例验证。 3分钟坐10元地铁，得票，花费10；46分钟坐5元公交，票没过期且10≥5，用票，免费；50分钟坐12元地铁，得票，花费12；96分钟坐3元公交，12≥3，用票；110分钟坐5元地铁，得票，花费5；135分钟坐6元公交，手里5元的票比6元便宜，不能用，只好花6元。总花费是 10+12+5+6=36，和样例一致。

参考代码

// 公交换乘：地铁得优惠票（45分钟内可免费坐不超地铁价的公交），模拟花费
#include <iostream>
using namespace std;

int tp[100005];        // 优惠票对应的地铁票价
long long tt[100005];  // 优惠票获得的时间
int used[100005];      // 优惠票是否已被使用

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, ty, p, i;
    long long t, total = 0;
    int head = 0, tail = 0;  // 优惠票队列的头尾指针
    cin >> n;
    while (n--) {
        cin >> ty >> p >> t;
        if (ty == 0) {              // 地铁：必须花钱，获得一张优惠票
            tp[tail] = p;
            tt[tail] = t;
            tail++;
            total += p;
        } else {                    // 公交车：先清除过期的优惠票
            while (head < tail && t - tt[head] > 45) head++;
            int flag = 0;
            for (i = head; i < tail; i++) {
                if (!used[i] && tp[i] >= p) {  // 最早获得且票价比车费高的
                    used[i] = 1;
                    flag = 1;
                    break;
                }
            }
            if (!flag) total += p;  // 没有可用优惠票就要付钱
        }
    }
    cout << total << "\n";
    return 0;
}

复杂度分析

每条出行记录最多会扫描一遍当前队列里的优惠票，最坏情况下时间会达到 O(n²)。不过因为优惠票45分钟后就过期、会被从队头清除，队列通常很短，而且数据规模 n≤100000，实际测试中最大的数据也只跑了几十毫秒，完全能通过。空间上保存优惠票的三个数组大小都和 n 同级别，空间复杂度是 O(n)。