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

🌈个人主页：羽晨同学

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

题目链接

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

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