洛谷 P5661 题解

1. 题目简述

买一张地铁票可以获得一张用于公交车且有效期为45分钟的等值的无门槛优惠券，优惠券只能抵票。现在给出乘坐信息，求花的钱。（优惠券可以累积，搭乘公交时，有优惠券就用优惠券，若有多张优惠券可用，需要使用最早获得的优惠券。）

2. 解题方法

使用链表的 next 来实现删除以使用的优惠券。把新地铁票（优惠券）“push”到链表的末尾。

3. code （有一个小提示，详见https://www.luogu.com.cn/discuss/476413）

#include<iostream>
#include <cstring>
#define MAX 100000
using namespace std;
int head=0,tail=0,tik[MAX][3];
//head:链表的头  tail:链表的尾  tik[][0]:price  tik[][1]:t tik[][2]:指向下一个的指针(price,t的含义详见题目)
bool het(){return head==tail;}//检查链表是否为空
int push(int p,int t)//存放地铁票(优惠信息)(p=price,t=t)
{
	
	tik[tail][0]=p;
	tik[tail][1]=t;
	tik[tail][2]=tail+1;
	tail++;
	return 0;
}
bool check(int p)//检查有没有可用的优惠券，若有就删除第一个可用的优惠券并return 1，若无则return 0。
{
	int num=head,tmp=-1;
	while(num<tail)
	{
		
		if(p<=tik[num][0])
		{
			if(tmp!=-1)tik[tmp][2]=tik[num][2];
			else head=tik[num][2];
			return 1;
		}
		tmp=num;
		num=tik[num][2];
		
	}
	return 0;
}
int update(int t)//检查并删除不满足时间限制的优惠券。
{
	if(het())return 0;
	if((t-tik[head][1])>45)
	{
		head=tik[head][2];
		update(t);
	}
	return 0;
}
int main()
{
	int n=0,ans=0;
	scanf("%d",&n);
	for(int i=0;i<n;++i)
	{
		int bos;//表示是公交车还是地铁
		int m,t;
		scanf("%d%d%d",&bos,&m,&t);
		if(bos)//若是公交车
		{
			update(t);//则检查并删除不满足时间限制的优惠券
			if(!check(m))ans+=m;//且若没有可用的优惠券，则直接支付。
		}
		else//若是地铁
		{
			push(m,t);//则增加优惠券
			ans+=m;//并且支付买地铁票的钱
		}
	}
	printf("%d",ans);//输出答案(虽然大家都知道，但还是要讲)
	return 0;
}

浏览次数: