题解：P5661 [CSP-J2019] 公交换乘

思路

模拟题。

在《深入浅出基础版》中介绍过这类题目，这类题目一般只需按照题意模拟，特殊情况时需要使用数据结构及优化。

思路也很简单，直接暴力，乘坐地铁时，花费价格直接加到总和。

否则往前枚举，首先，如果时间相差超过

45

分钟，直接结束。之后判断：如果乘坐的是地铁，花费的价格更高，且优惠卷没被使用，那就使用优惠卷，否则原价购买。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
long long n,ans,b[100005],mi;
struct kun{
	long long p,t;// price 价格，time 时间
	bool c;//c 乘车种类
}a[100005];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].c>>a[i].p>>a[i].t;
		b[i]=1;//标记优惠卷未使用。
	} 
	for(int i=1;i<=n;i++){
		if(a[i].c==0) ans+=a[i].p;//如果是地铁直接坐。
		else{//如果是公交车，考虑使用优惠卷。
			mi=-1;
			for(int j=i-1;j>=1;j--){//枚举他前面的乘车记录。
				if(a[i].t-a[j].t>45) break;
				if(a[j].p>=a[i].p&&a[j].c==0&&b[j]==1){
					mi=j;
				}//满足要求。
			}
			if(mi==-1) ans+=a[i].p;
			else b[mi]=0;	//记得标记已使用。
		}		
	}
	cout<<ans;
	return 0;
}

题解：P5661 [CSP-J2019] 公交换乘

文章操作

思路

代码

相关推荐

评论

题解：P5661 [CSP-J2019] 公交换乘