# CSP-J 2019 公交换乘## 题目描述著名旅游城市 B 市为了鼓励大家采用公共交通方式出行推出了一种地铁换乘公交车的优惠方案：1 在搭乘一次地铁后可以获得一张优惠票有效期为 45 分钟在有效期内可以消耗这张优惠票免费搭乘一次票价不超过地铁票价的公交车。在有效期内指开始乘公交车的时间与开始乘地铁的时间之差小于等于 45 分钟即：$t_bus - t_subway leq 45$2 搭乘地铁

思路

本题一眼看上去是一道模拟题，但是如果真的模拟的话，复杂度会达到 $O(n^2)$，无法通过此题。

我们考虑一下优化思路。对于每一次搭乘地铁，我们需要记录当前获得的优惠票的数量和最后一张优惠票的开始时间。每一次搭乘公交车，我们需要找到满足条件的最早的优惠票并使用它。

我们可以用两个栈来分别记录当前获得的优惠票和已经使用的优惠票。每一次搭乘地铁时，我们将当前获得的优惠票入栈。每一次搭乘公交车时，我们将已经使用的优惠票出栈，直到找到满足条件的最早的优惠票。在这个过程中，我们需要判断已经出栈的优惠票是否还在有效期内，如果在则将其重新入栈。如果已经使用的优惠票不能满足条件，那么我们就需要花费当前公交车的票价，并将此次乘车的记录入栈。

需要注意的是，优惠票的开始时间是记录搭乘地铁的时间，而不是记录获得优惠票的时间。因此，每一次搭乘地铁时，我们需要记录下当前的时间并与栈顶元素的开始时间做比较，判断是否需要将栈顶元素出栈。

具体实现时，我们可以用一个结构体 Ticket 来表示优惠票，包含以下成员：

• price：表示优惠票的面额，即能够抵消的公交车票价。
• start_time：表示优惠票的开始时间，即搭乘地铁的时间。

对于已经使用的优惠票，我们可以直接使用一个变量 used_time 来表示它的开始时间。

总时间复杂度为 $O(n)$。

代码

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

struct Ticket {
    int price, start_time;
    Ticket(int p, int t) : price(p), start_time(t) {}
};

int main() {
    int n;
    cin >> n;
    stack<Ticket> tickets; // 当前获得的优惠票
    stack<int> used_tickets; // 已经使用的优惠票
    int cost = 0, used_time = -1; // used_time 表示最后一张使用的优惠票的开始时间
    for (int i = 0; i < n; i++) {
        int type, price, time;
        cin >> type >> price >> time;
        if (type == 0) { // 搭乘地铁
            tickets.push(Ticket(price, time));
            while (!tickets.empty() && time - tickets.top().start_time > 45) {
                tickets.pop(); // 将已经过期的优惠票出栈
            }
        } else { // 搭乘公交车
            while (!used_tickets.empty() && time - used_tickets.top() > 45) {
                tickets.push(Ticket(price, used_tickets.top())); // 将已经过期的优惠票重新入栈
                used_tickets.pop();
            }
            if (!tickets.empty() && tickets.top().price >= price && (used_time == -1 || time - tickets.top().start_time < time - used_time)) {
                // 如果有优惠票可用，则使用优惠票
                used_time = tickets.top().start_time;
                used_tickets.push(tickets.top().start_time);
                tickets.pop();
            } else {
                // 没有可用的优惠票，则花费当前公交车的票价
                cost += price;
            }
        }
    }
    cout << cost << endl;
    return 0;
}
``