luogu-P5661 公交换乘

104 阅读 0 评论 69 点赞

我是靠谱客的博主顺心花生，这篇文章主要介绍luogu-P5661 公交换乘，现在分享给大家，希望可以做个参考。

题目连接

该题是CSP-J2-2019-T2

题目大意

可以选乘公车或者地铁；
乘坐地铁时：一定要买票，但会获得（45分钟内有效）的免费公车券；
乘坐公车时：有券一定用券（而且先用早的券），没券则买票；
问：最小的花费。

题目分析

根据~~NOIP~~的惯例，这个T2也应该是签到题，大胆地想模拟。
结果发现，真的是个大模拟，注意细节就好。

参考代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//CSP-J2-2-公交换乘
//贪心模拟 
#include<bits/stdc++.h>
using namespace std;
int n;
long long ans;
struct nod{
	int w,t;
};
vector<nod>q;

int main(){
	cin>>n;
	int x,w,t;
	while(n--){
		scanf("%d %d %d",&x,&w,&t);
		
		if(x==0){	//坐地铁，一定要买票 
			q.push_back({w,t});
			ans+=w;
		}
		
		while(!q.empty()&&t-q.front().t>45)	//扔掉过期的券
			q.erase(q.begin(),q.begin()+1);	 
			
		if(x==1){	//坐公交
			bool ff=0;
			if(!q.empty()){	
				int len=q.size();
				for(int i=0;i<len;i++){
					if(q[i].w>=w){	//有优惠券，用掉 
						ff=1;
						q.erase(q.begin()+i,q.begin()+i+1);
						break;
					}
				}
			} 
			if(!ff) ans+=w;	//没券，买票 
		}
	}
	
	cout<<ans;
	
	return 0;
}