公交换乘

题目大意
在搭乘一次地铁后可以获得一张优惠票，45 分钟内必须消耗这张优惠票，免费搭乘一次票价不超过优惠票价的公交车

思路分析
每次遇到地铁直接花钱，遇到公交车时遍历之前的所有乘地铁后可用的优惠票，使用最前一张可用的优惠票抵掉本次的钱

代码实现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,ans;
//标记那张可以用作优惠票
bool vis[100010];
//按题目输入建立结构体
struct node{
	ll veh;
	ll price;
	ll t;
}a[100010];
int main(){
	cin >> n;
	for(int i = 1;i <= n;i++){
		cin >> a[i].veh >> a[i].price;
		cin >> a[i].t;
	}
	for(int i = 1;i <= n;i++){
        if(a[i].veh == 0) ans += a[i].price; //如果是地铁只能花钱
        else{
            vis[i] = 1;                      //记录当前乘车不能作为优惠票
            ll f = 0;
            for(int j = i - 1;j >= 1;j--){
            //当前j是公交车 或 当前已经不能作为优惠票,去看下一个
                if(a[j].veh == 1 || vis[j]) continue;
            //当前已经超出时间(因为时间是顺序的,从后往前遍历时当前时间超出了,后面都看不了了)
            //因为超出45分钟就break,所以这层循环最多循环45次,不会超时
                if(a[i].t - a[j].t > 45) break;
            //只有当前价钱小于优惠票时才能使用
                if(a[i].price <= a[j].price) f = j;
            }
            //如果没有优惠票可用,只能花钱
            if(f == 0) ans += a[i].price;
            //用了优惠票,标记这张票不再可用
            else vis[f] = 1;
        }
    }
    cout << ans;
	return 0;
}