【2019CSP-J普及组】T2 公交换乘

92 阅读 0 评论 61 点赞

我是靠谱客的博主不安冬天，这篇文章主要介绍【2019CSP-J普及组】T2 公交换乘，现在分享给大家，希望可以做个参考。

P5661 公交换乘
题目传送门

思路：
根据题意，我们可以分为两种情况讨论

乘地铁，上车买票送券
乘公交，是否免票（队列）
考虑几个细节：
优惠券过期，直接作废（时间升序）；
优惠券金额不够，下一张；
无适合的优惠券，买票。

复制代码

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
47
48
49
50
51
52
53
54
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);
using namespace std;
const int MAX=2147483647;
const int N=1e6;
struct node
{
	int by,t,p;
} a[N];
int n,head=1,tail,ans,que[2*N][3];
void input()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i].by,&a[i].p,&a[i].t);
}
int main()
{
	//fre();
	input();
	for(int i=1;i<=n;i++)
	{
		if(!a[i].by) //地铁 
		{
			que[++tail][0]=a[i].t+45; //优惠券有效期 
			que[tail][1]=a[i].p;      //优惠券票价 
			ans+=a[i].p;         //坐地铁买票 
		}
		else  //公交 
		{
			bool flag=0;
			for(int j=head;j<=tail;j++)  
			{
				if(a[i].t>que[j][0]) head++; //过期作废 
				else if(a[i].p<=que[j][1]&&!que[j][2])  
				//票价要不大于优惠券金额且没用过 
				{
					que[j][2]=1;
					flag=1;
					break;	
				}
			}
			if(!flag) ans+=a[i].p;  //不能免票，买票 ！ 
		}
	}
	printf("%d",ans);
	return 0;
}