P5661 公交换乘题解

泥土笨笨 · 2019-11-17 11:18:04 · 题解

拿到题目看一下，大体思路还是比较清晰的，用一个数组来装所有的收集到的赠票。每当坐地铁的时候，就直接花钱，然后获得一张赠票，放到数组里面。每当坐公交的时候，看看数组里面有没有时间合适，价格小于现在公交票价的赠票，并且没用过的赠票，直接用时间最早的那一张就可以了。

每张赠票要存三个信息，因此用一个结构体来存。数据不超过10^5，因此开一个10^5长度的数组。

const int MAXN = 100005;
struct Ticket {
    //赠票的价格，最晚使用时间和是否需用过
    int price, time, used;
} q[MAXN];//赠票盒子

然而，出题人会这么善良么？显然不会。我们想想极限情况什么样子，极限数据10^5，假设开始的时候全坐地铁，坐了5*10^4 次以后，我们的盒子里面有好多票啊。后面全坐公交，要坐5*10^4 次，每次都在这个大盒子里面找合适的票，复杂度O(n^2),总计算量2.5*10^9，我们在超时的边缘疯狂试探啊。

怎么优化呢?关键点在于题中说每次坐车开始时间都不重合，而且45分钟票就过期。所以理论上来讲，盒子里最多也就有45张没过期的票。大量的票都是已经过期了的，没必要从头扫一遍数组，在大量过期的票中浪费宝贵的青春。所以我们想到类似手写队列的方法，定义一个head变量和一个tail变量，分别表示目前还没过期的第一张票的位置，和下一张新的赠票在数组里要插入的位置，每次从head到小于tail循环即可。每次最多循环45次，总共10^5次循环，肯定不会超时。

其余细节看代码注释吧。不要复制粘贴哦。

#include <iostream>

using namespace std;
const int MAXN = 100005;
struct Ticket {
    //赠票的价格，最晚使用时间和是否需用过
    int price, time, used;
} q[MAXN];//赠票盒子
int head, tail, n, cost;

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int op, price, time;
        //输入每次坐车的种类，价格和发车时间
        cin >> op >> price >> time;
        if (op == 0) {
            //如果是坐地铁，直接把价格加到cost里面
            cost += price;
            //新一张赠票插入数组末尾，这张票的最晚使用时间是当前时间+45
            q[tail].time = time + 45;
            //赠票面额就是地铁票价
            q[tail++].price = price;
        } else {
            //先用一个循环把过期票扔掉
            while (head < tail && q[head].time < time) {
                head++;
            }
            bool found = false;//表示是否有合适的赠票，先假设没有
            for (int j = head; j < tail; ++j) {
                //循环所有剩余的票，这些一定都没过期，因为题目中时间是按顺序给我们的
                if (q[j].price >= price && q[j].used == 0) {
                    //如果价格合适，并且没用过，标记找到了，这张票标记用过
                    found = true;
                    q[j].used = 1;
                    break;
                }
            }
            //如果没找到合适的赠票，老老实实花钱买吧
            if (!found) cost += price;
        }
    }
    cout << cost << endl;
    return 0;
}

P5661 公交换乘 题解

P5661 公交换乘题解