没人水题解？我来一发

首先这个题，意思应该很简单，就是计算最小花费。

先直接考虑暴力做法，我们定义一个结构体，结构体两个变量$price$和$t$代表价格和时间，然后我们去输入就行，输入的地铁票先全部存起来，输入了公交车以后，我们去暴力遍历已经有的地铁票去比较就行了。

因此做出如下暴力代码可获得$30$分。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n, ans, opt;
struct node
{
	int price, t;
};
vector<node> v;
bool vis[100005];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		node x;
		cin >> opt >> x.price >> x.t;
		if (opt == 0)
		{
			v.push_back((node){x.price, x.t});
			ans += x.price;
		}
		else
		{
			bool flag = true;
			for (int j = 0; j < v.size(); j++)
			{
				if (!vis[j] && v[j].price >= x.price && x.t - v[j].t <= 45)
				{
					vis[j] = true;
					flag = false;
					break;
				}
			}
			if (flag)
				ans += x.price;
		}
	}
	cout << ans;
	return 0;
}

其中$vis$数组标记每一个是否用过，$if$语句三个条件，没用过，并且价格贵，并且还没过期。

这样做只能$30$分，主要在于存储的地铁票可能大部分早早就过期了，导致我们下面的$for$循环执行了很久，所以我们在存储地铁票的时候，加一个判断就行了，如果当前地铁票已经过期，就不管了。因此设置一个$head$变量初始为$0$，指向$vector$的第一个元素位置，然后如果过期就$head++$

底下的循环就从$head$开始遍历即可

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n, ans, opt, head;
struct node
{
	int price, t;
};
vector<node> v;
bool vis[100005];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		node x;
		cin >> opt >> x.price >> x.t;
		if (opt == 0)
		{
			v.push_back((node){x.price, x.t});
			if (x.t - v[head].t > 45)
				head++;
			ans += x.price;
		}
		else
		{
			bool flag = true;
			for (int j = head; j < v.size(); j++)
			{
				if (!vis[j] && v[j].price >= x.price && x.t - v[j].t <= 45)
				{
					vis[j] = true;
					flag = false;
					break;
				}
			}
			if (flag)
				ans += x.price;
		}
	}
	cout << ans;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
struct ticket{
	int f,p,t;//f指乘的种类0地铁，1公交车  p价格 t时间 
};
ticket ts[100005];
int main()
{
	//输入交通记录
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>ts[i].f>>ts[i].p>>ts[i].t;
	} 
	//计算花费
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		//如果是地铁,将费用加到ans
		if(ts[i].f==0)
		{
			ans+=ts[i].p;
		}
		//如果是公交车，从前往后查看是否优惠票
		else
		{
			int inx=-1;
			for(int j=i-1;j>=1 && ts[i].t-ts[j].t<=45;j--)
			{//只要枚举当前公交车时间前面45分钟，从i-1开始倒推45分钟，时间复杂度大大降低
				if(ts[j].f==0 && ts[j].p>=ts[i].p) //查找符合条件的优惠票 
				{
					inx=j; 
					//后面不能用break, 因为要用最前面的符合条件的优惠票(例倒推45分钟有两张优惠券,例如前面25分钟（要退出）,无法用前面15分钟
				}//如果倒推45分钟有两张优惠券，例如前面25分钟，inx=25 ,再循环前面15分钟也符合，inx=15
				
			}
			if(inx!=-1)//有优惠票 
			{
				ts[inx].f=-1;//将第15分钟的标记为-1 ，说明已经使用了，不要加钱。而前面25分钟那张优惠票,没有标记,没有用 
			}
			else//没有优惠票，就加公交车车票价格 
			{
				ans+=ts[i].p;	
			 } 	 
		 } 
	 }
	 cout<<ans;	
	return 0;
}#include<bits/stdc++.h>
using namespace std;
struct ticket{
	int f,p,t;//f指乘的种类0地铁，1公交车  p价格 t时间 
};
ticket ts[100005];
int main()
{
	//输入交通记录
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>ts[i].f>>ts[i].p>>ts[i].t;
	} 
	//计算花费
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		//如果是地铁,将费用加到ans
		if(ts[i].f==0)
		{
			ans+=ts[i].p;
		}
		//如果是公交车，从前往后查看是否优惠票
		else
		{
			int inx=-1;
			for(int j=i-1;j>=1 && ts[i].t-ts[j].t<=45;j--)
			{//只要枚举当前公交车时间前面45分钟，从i-1开始倒推45分钟，时间复杂度大大降低
				if(ts[j].f==0 && ts[j].p>=ts[i].p) //查找符合条件的优惠票 
				{
					inx=j; 
					//后面不能用break, 因为要用最前面的符合条件的优惠票(例倒推45分钟有两张优惠券,例如前面25分钟（要退出）,无法用前面15分钟
				}//如果倒推45分钟有两张优惠券，例如前面25分钟，inx=25 ,再循环前面15分钟也符合，inx=15
				
			}
			if(inx!=-1)//有优惠票 
			{
				ts[inx].f=-1;//将第15分钟的标记为-1 ，说明已经使用了，不要加钱。而前面25分钟那张优惠票,没有标记,没有用 
			}
			else//没有优惠票，就加公交车车票价格 
			{
				ans+=ts[i].p;	
			 } 	 
		 } 
	 }
	 cout<<ans;	
	return 0;
}