题意

模拟题。 如果是地铁，拿票付费。 如果是公交： 1.有票用票。 2.没票付费。 那么就很煎蛋了。

思路

首先，下意识就是一个数组存放票。 票有三个信息： 1.票价。 2.开始时间。 3.结束时间。 开始时间是不用存的，因为你的公交一定在你要用的票的后面。 so？

struct ticket{
  int value;
  int time;
}

然后我们发现会有大量过期票囤积，有可能会TLE（反复循环过期部分）。 所以一定要清掉过期的票。 怎么清理呢？前面说了是用数组，所以在现实层面上的清理是不现实的，时间复杂度仍为$O(n^2)$。 那想要把清理的难度降至$O(n)$，有一个好办法就是像手写队列一样，放上front和tail。 然后就是模拟啦。

代码

#include<iostream>
#define N int(2e5)//懂得都懂啊
using namespace std;
struct ticket{//优惠票
	int value;//票价
	int time;//endtime
};
struct box{//票箱
	ticket a[N];
	int front=1;//队列思想
	int tail=1;
}; 
int main(){
	int n(0);/
	cin>>n;
	box a;//这个需要说吗？需要请回复。
	int cost(0);//总花费的钱数
	for(int i(1);i<=n;i++){
		int mod(0);//坐的什么车
		int price(0);//价格
		int t(0);//时间
		cin>>mod>>price>>t;
		if(mod==0){//坐地铁
			a.a[a.tail++]={price,t+45};//拿票，价格为车费，结束时间为四十五分钟后
			cost+=price;//只能付费
		}
		else{
			while(a.a[a.front].time<t)
				a.front++;//把过期的票退掉
			bool ready(0);//有没有票能用
			for(int i(a.front);i<a.tail;i++)
				if(a.a[i].value>=price){
					ready=1;
					a.a[i].value=0;//把票清0
					break;
				}
			if(!ready)//要是无票可用
				cost+=price;//花钱
		}
	}
	cout<<cost;
	return 0;
}

公告

想和我交朋友的点一下。

#include<bits/stdc++.h>
using namespace std;
struct s{
    int t,m;
}arr[int(1e5)];
int main(){
    int n,ans=0,l=0,r=0;
    cin>>n;
    while(n--){
        int a,b,c;
        cin>>a>>b>>c;
        if(a==0)
            arr[r++]={c,b},ans+=b;//存优惠票+付钱
        bool flag=0;
        if(a==1){
            for(int i=l;i<r;i++){
                if(c-arr[i].t>45)
                    l=i;//超时废掉
                else if(b<=arr[i].m){
                    arr[i].m=-1;//用了废掉
                    flag=1;
                    break;
                }
            }
            if(flag==0) ans+=b;//没用优惠卷付钱
        }
    }
    cout<<ans;
    return 0;
}