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

P5661 公交换乘
题目传送门

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

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

#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;
}

最后

以上就是不安冬天为你收集整理的【2019CSP-J普及组】T2 公交换乘的全部内容，希望文章能够帮你解决【2019CSP-J普及组】T2 公交换乘所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。