当前位置：首页 > article >正文

蓝桥杯每日一题----海底高铁

article 2025/3/25 13:24:47

🌈个人主页：羽晨同学

💫个人格言:“成为自己未来的主人~”

题目链接

P3406 海底高铁 - 洛谷https://www.luogu.com.cn/problem/P3406

解题思路

在这道题来说，主要使用的想法就是使用一维的差分数组，这道题中有两个买票的策略。

一种是，直接买票，另外一种是买IC卡并买带有优惠的票。

其实解题思路蛮简单的，我们只要找到每个城市去的次数，再加上每段路程最小的花费，就是总的最小的花费。

而我们在获取每段路程的次数上，就可以使用差分的方式。

比如说，从1,3，那么可以设为1为L，3为R。K为1，当中的路径每个+1.

完整代码

#include<iostream>
using namespace std;
const int N = 1e6+10;
typedef long long LL;
LL f[N];//差分数组
int main()
{
	int n,m;cin>>n>>m;
	//差分数组初始化
	int x;cin>>x;
	for(int i=2;i<=m;i++)
	{
		//x->y
		int y;cin>>y;
		if(y>x)//y=r
		{
			f[x]++;f[y]--;	
		}
		else
		{
			f[x]--;f[y]++;	
		}
		x=y; 
	} 
	LL ret = 0;
	//改变到原数组 
	for(int i=1;i<=n;i++) f[i]+=f[i-1];
	for(int i=1;i<n;i++)
	{
		int a,b,c;cin>>a>>b>>c;
		ret +=min(a*f[i],c+b*f[i]);
	}
	cout<<ret<<endl;
	return 0;	
}

好了，今天的内容就到这里，我们明天再见。