2019 公交换乘 · 方案一暴力匹配

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 2/5 · 共 1406 字

按获得顺序找第一张能用的优惠票

2019
模拟

正文

// CSP-J 2019 复赛 T2 · 公交换乘
// 原题：https://oj.yecheng.tv/p/CSPJ2019B
// 题意：坐一次地铁得一张优惠票，45 分钟内可免费坐一次票价不超过地铁票价的公交；
// 票可以攒着，用的时候优先消耗最早获得的那张。求总花费。
//
// 方案一 · 暴力匹配（照题意直写，n 大时会超时）
// 用一个 tickets 数组按获得顺序记下每张票的票价、时间与是否已用。
// 遇到一条公交记录，就从最早那张开始往后找第一张
// 「没过期、没用过、票价又够高」的票，找到就免单。
// 每张公交最坏要扫一遍全部票，总复杂度 O(n^2)，只能过小数据。

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

struct Ticket {
    int price;   // 这张票对应那次地铁的票价
    int time;    // 坐地铁的时刻
    bool used;   // 是否已被消耗
};

int main() {
    freopen("transfer.in", "r", stdin);
    freopen("transfer.out", "w", stdout);

    int n;
    cin >> n;

    vector<Ticket> tickets;
    int cost = 0;

    for (int i = 0; i < n; i++) {
        int kind, price, t;
        cin >> kind >> price >> t;
        if (kind == 0) {
            // 地铁：付钱，并领到一张优惠票
            tickets.push_back({price, t, false});
            cost += price;
        } else {
            bool freeRide = false;
            for (int j = 0; j < (int)tickets.size(); j++) {
                if (tickets[j].used) continue;
                if (t - tickets[j].time > 45) continue;   // 超过 45 分钟，票已过期
                if (tickets[j].price < price) continue;   // 票价不够高，用不了
                tickets[j].used = true;                   // 用掉最早能用的那张
                freeRide = true;
                break;
            }
            if (!freeRide) cost += price;
        }
    }

    cout << cost << "\n";
    return 0;
}

2019 公交换乘 · 方案一 暴力匹配

正文

CSP-J 标程 · 复赛真题的其它内容

2019 公交换乘 · 方案一暴力匹配