P5661 [CSP-J2019] 公交换乘

那么这道题我们先分析一下题目：题目先输入n行乘车记录，0 代表地铁，1 代表公交车，然后一个price和一个Time，让我们求最少的花费

那么我们想到的贪心思路：

1.定义结构体和两个队列

2.输入n

3.在输入的循环里，每输入一张票，判定它的种类

4.地铁：直接花钱，把优惠票塞进第一个队列

5.大巴：

（1）从头，把过期的优惠票弹出

（2）从头，如果钱比大巴的少弹入第二个队列，如果够了就标记已找到并弹出当前票。

（3）把剩下的优惠票塞进第二个队列

（4）两个队列互换

（5）假如没找到票就花钱

6.输出

---

代码：

#include<bits/stdc++.h>
using namespace std;
//定义结构体行程票 
struct ticket{
	int kind;
	int time;
	int money;
}a[100005];
//定义两个队列 
queue <ticket> q[2];
int n,in;//n和队列下标 
int main()
{
	int i,ans=0;
	bool f;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		f=false;//判断是否找到优惠票 
		cin>>a[i].kind>>a[i].money>>a[i].time;
		if(a[i].kind==0)//地铁票 
		{
			ans+=a[i].money;//地铁直接花钱 
			q[in].push(a[i]);
			continue;//跳过大巴票的程序 
		}
		while(!q[in].empty()&&a[i].time-q[in].front().time>45)  q[in].pop();//过期的弹出
		//从头开始搜优惠票 
		while(!q[in].empty())
		{
			if(q[in].front().money>=a[i].money)//找到了 
			{
			    f=true;
				q[in].pop();
				break;
			}
			//弹入第二个队列，自己弹出 
			q[1-in].push(q[in].front());
			q[in].pop();
		}
		//把剩下的票扔进第二个队列 
		while(!q[in].empty())
		{
			q[1-in].push(q[in].front());
			q[in].pop();
		}
		if(!f)  ans+=a[i].money;//没找到，花钱 
		in=1-in;//变换队列下标 
	} 
	cout<<ans<<endl;//输出 
	return 0;
}

这道题潮水潮水的，不AC才怪