东莞站福公司工资/模板免费网站建设
🌈个人主页:羽晨同学
💫个人格言:“成为自己未来的主人~”
题目链接
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;
}
好了,今天的内容就到这里,我们明天再见。