题目：
样例解释：
样例#1：
第一条记录，在第 3 分钟花费 10 元乘坐地铁。
第二条记录，在第 46 分钟乘坐公交车，可以使用第一条记录中乘坐地铁获得的优惠票，因此没有花费。
第三条记录，在第 50 分种花费 12 元乘坐地铁。
第四条记录，在第 96 分钟乘坐公交车，由于距离第三条记录中乘坐地铁已超过 45 分钟，所以优惠票已失效，花费 3 元乘坐公交车。
第五条记录，在第 110 分钟花费 5 元乘坐地铁。
第六条记录，在第 135 分钟乘坐公交车，由于此时手中只有第五条记录中乘坐地铁获得的优惠票有效，而本次公交车的票价为 6 元，高于第五条记录中地铁的票价 5 元，所以不能使用优惠票，花费 6 元乘坐公交车。
总共花费 36 元。
样例#2：
第一条记录，在第 1 分钟花费 5 元乘坐地铁。
第二条记录，在第 16 分钟花费 20 元乘坐地铁。
第三条记录，在第 23 分钟花费 7 元乘坐地铁。
第四条记录，在第 31 分钟乘坐公交车，此时只有第二条记录中乘坐的地铁票价高于本次公交车票价，所以使用第二条记录中乘坐地铁获得的优惠票。
第五条记录，在第 38 分钟乘坐公交车，此时第一条和第三条记录中乘坐地铁获得的优惠票都可以使用，使用获得最早的优惠票，即第一条记录中乘坐地铁获得的优惠票。
第六条记录，在第 68 分钟乘坐公交车，使用第三条记录中乘坐地铁获得的优惠票。
总共花费 32 元。
样例#3：
第一条记录，在第 1 分钟花费 5 元乘坐地铁。
第二条记录，在第 16 分钟花费 6 元乘坐地铁。
第三条记录，在第 23 分钟花费 10 元乘坐地铁。
第四条记录，在第 47 分钟乘坐公交车。此时由于距离第一条记录中乘坐地铁已超过 45 分钟，所以优惠票已失效；第二，三条记录中的优惠票有效，但本次公交票价为 7 元，高于第二条的优惠票，只有第三条记录中的优惠票可以使用，所以使用第三条记录的优惠票。
第五条记录，在第 50 分钟乘坐公交车，此时第二，三条记录的优惠票有效，但第三条记录的优惠票已经使用，第二条记录的优惠票高于本次公交票价，所以使用第二条记录的优惠票。
第六条记录，在第 55 分钟乘坐公交车，第一条记录的优惠票已失效，第二，三条记录的优惠票已使用，花费 10 元乘坐公交车。
总共花费 31 元。
思路：
用一个数组来装所有的收集到的赠票。每当坐地铁的时候，就直接花钱，然后获得一张赠票，放到数组里面。每当坐公交的时候，看看数组里面有没有时间合适，价格小于现在公交票价的赠票，并且没用过的赠票，直接用时间最早的那一张就可以了。
每张赠票要存三个信息，因此用一个结构体来存。数据不超过105105，因此开一个105105长度的数组。
const int MAXN = 100005;
struct Ticket {//赠票的价格，最晚使用时间和是否需用过int price, time, used;
} q[MAXN];//赠票盒子然而，出题人会这么善良么？NO，NO，NO，显然不会。我们想想极限情况什么样子，极限数据105105，假设开始的时候全坐地铁，坐了5∗1045∗104 次以后，我们的盒子里面有好多票啊。后面全坐公交，要坐5∗1045∗104 次，每次都在这个大盒子里面找合适的票，复杂度O(n2)O(n2),总计算量2.5∗1092.5∗109，我们在超时的边缘疯狂试探啊。
怎么优化呢?关键点在于题中说每次坐车开始时间都不重合，而且45分钟票就过期。所以理论上来讲，盒子里最多也就有45张没过期的票。大量的票都是已经过期了的，没必要从头扫一遍数组，在大量过期的票中浪费宝贵的青春。所以我们想到类似手写队列的方法，定义一个head变量和一个tail变量，分别表示目前还没过期的第一张票的位置，和下一张新的赠票在数组里要插入的位置，每次从head到小于tail循环即可。每次最多循环45次，总共105105次循环，肯定不会超时。
其余细节看代码注释吧。不要复制粘贴哦，理解题目才是王道！！！
#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;//新一张赠票插入数组末尾，这张票的最晚使用时间是当前时间+45q[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;
}
