CSP-J2019真题——公交换乘

115 阅读 0 评论 76 点赞

我是靠谱客的博主俊秀小鸽子，这篇文章主要介绍CSP-J2019真题——公交换乘，现在分享给大家，希望可以做个参考。

话不多说，先求拉票。
博客之星的评选，谢谢！

在这里插入图片描述
这个题很nice的。

复制代码

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
//Author:PanDaoxi
#include <iostream>
using namespace std;
struct ticket{
	int x,y;
}p[1000001];
int main(){
	int n,a,b,c,f1,f2,sum,t;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a>>b>>c;
		if(a==0){ //地铁 
			p[f1].x=b; //记录 
			p[f1].y=c;
			f1++;
			sum+=b; //加钱 
		}
		else{ //公交 
			f2=0;
			for(int j=t;j<f1;j++){
				if(c-p[j].y<=45&&b<=p[j].x){ //不超过地铁 
					p[j].x=-1;
					f2=1;
					break;
				}
				else if(c-p[j].y>45){ //时间超出 
					t=j+1; 
				}
			}
			if(!f2) sum+=b; 
		}
	}
	cout<<sum<<endl;
	return 0;
}

我很无语，系统刷题的时候再刷到，再写。

复制代码

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
//Author:PanDaoxi
#include <iostream>
using namespace std;
struct piao{
	int p,t;
	bool u;
	// 增票价格、最晚时间、是否用过
} q[10000001]; // 赠的票
int main(){
	int h,t,n,m;
	h=t=m=0;
	cin>>n;
	for(int i=0;i<n;i++){
		int types,price,time;
		cin>>types>>price>>time;
		if(types==0){
			// 地铁
			m+=price;
			q[t++].t=time+45;
			q[t-1].p=price;
		}
		else{
			// 抛弃过期的
			while(h<t&&q[h].t<time){
				h++;
			}
			bool find=false; // 假设没有合适的票
			for(int j=h;j<t;j++){
				if(q[j].p>=price&&!q[j].u){
					find=true;
					q[j].u=true;
					break;
				}
			}
			// 没票了，买吧
			if(!find) m+=price;
		}
	}
	cout<<m;
	return 0;
}