接模拟

为了方便使用，我们不妨把每一个地铁的信息按照优惠票的信息来储存。开一个结构体数组，来储存优惠票的信息（有效时间 + 最高价钱 + 使用与否）。与输入唯一的区别在于：把乘地铁的时间+45min变成优惠票的有效期即可。

对于某次乘公交车能使用某个优惠票，需要满足四个条件：

1.在乘坐公交车之前获得该优惠票

2.乘坐公交车的时间在优惠票有效时间内

3.乘坐公交车的价钱在优惠票的最高价钱内

4.优惠票没被使用

对于第一条，由于输入按照时间顺序，所以可以边输入边判断能否使用优惠票，此时所有的优惠票一定都在坐公交车之前获得

对于第二条，由于输入按照时间顺序，所以可以在枚举每一次坐公交车时，用一个变量来​维护目前可以使用的最近有效期​，所有有效期早于此的优惠票都作废，不用考虑了

对于第三、四条，在循环里判断即可

因为乘车时间不会重复，这样 O(45*N) 复杂度可以过

代码：

#include<bits/stdc++.h>
using namespace std;
int n,edg=1,a,b,c,stik=1,ans=0;
//a为输入的地铁或公交车，b为输入的票价，c为输入的乘坐时间，
//edg为可使用的最早的票，stik为目前所有优惠票的数量，ans为输出的钱数
bool us; //us用于记录乘坐某辆公交车需不需要花钱
struct node{
int t,pri;
bool r;
}tik[100005];
//用于储存每一张优惠票：t表示有效期，pri表示最高价格，r表示使用与否
int main(){
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a>>b>>c;
if(a==0)//乘地铁
{
ans+=b;//一定会花钱
tik[stik].pri=b;
tik[stik].t=c+45;
stik++;
}
else//乘公交
{
us=0;
while(tik[edg].t<c&&edg<stik) edg++;//更新edg，筛掉所有超过有效期的票 （第二条）
for(int j=edg;j<stik;j++)
{
if(tik[j].pri>=b&&tik[j].r==0)//如果票价小于优惠票票价上限（第三条），并且优惠票没被使用（第四条）
{
tik[j].r=1;
us=1;
break;
}
}
if(us==0) ans+=b;//若没有可用优惠票就花钱
}
}
cout<<ans;
return 0;
}

题解来自洛谷网友