【题解】[CSP-J 2019] 公交换乘

题目描述

题目大意

给出 \(n\) 次出行记录（地铁 或 公交车），有以下优惠方案：

1. 搭乘一次地铁后可以获得一张有效期为45分钟的优惠票，可以免费搭乘一次票价不超过该地铁票价的公交车。
2. 优惠票可以累计存储
3. 优先使用过期时间早的优惠票。

思路

枚举每一次出行：

• 如果是地铁。累加花费，并记录优惠票。
• 如果是公交车。寻找优惠票抵消，特别的如果没有优惠票可以使用，需要累加花费。

代码

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

const int N = 1e5 + 5;
int n;

struct ticket // 定义结构体储存优惠票 
{
    int p; // 票价
    int t; // 过期时间
    bool vis; // 是否使用过 
};
ticket q[N]; // 用队列记录优惠票
int head, tail;

int main()
{
    scanf("%d", &n);

    int ans = 0; // 记录总花费
    while(n -- )
    {
        int opt, p, t; scanf("%d%d%d", &opt, &p, &t); // 分别输入 交通工具、票价、时间
        if (opt == 0) // 如果乘坐地铁
        {
            ans += p; // 将票价加到总花费上

            q[tail ++ ] = {p, t + 45, false}; // 记录优惠票（票价为 p，结束时间为 t+45，未使用）
        }
        else // 如果乘坐公交车
        {
            while (head < tail && q[head].t < t) // 剔除过期的优惠票
                head ++ ;

            bool f = false; // 记录是否使用了优惠票
            // 因为题目是按时间顺序给出的，所以第一张可以使用的优惠票，必定是最早的优惠票
            for (int i = head; i < tail; i ++ )
                if (q[i].vis == false && q[i].p >= p) // 如果找到了合适的优惠票
                {
                    q[i].vis = true; // 记录该优惠票已使用
                    f = true; // 记录使用了优惠票
                    break;
                }
            if (!f) // 如果没有找到合适的优惠票，就只能付钱
                ans += p; // 将票价加到总花费上
        }
    }
    printf("%d\n", ans); // 输出总花费

    return 0;
}