原题链接:https://www.luogu.com.cn/problem/P3406
题意解读:1-n个城市共了n段路,第i段路不买卡票价a[i],买卡票价b[i](卡本身花费c[i]),给定一个路程顺序,计算最少的通行费用。
解题思路:
根据路程,计算每段路各走了多少次,然后对于每段路,计算买卡和不买卡两种花费,取较小的累加即可。
如何计算每段路走了多少次?
1、朴素做法
枚举所有区间,再对区间内所有的路段,通过桶数组来标记走过的次数,时间复杂度n*m
2、差分
定义差分数组d[],对于每一个区间[l, r],执行d[l] += 1, d[r] -= 1,即可将该区间覆盖的所有路段都加1
然后,根据差分数组还原前缀和数组,即可枚举每段路走的次数,计算买卡和不买卡两种花费,取较小值累加。
100分代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int s[N]; //每一段路走了几次
int d[N]; //s的差分数组
int p[N]; //路径
int a[N], b[N], c[N];
int n, m;
long long ans;
int main()
{
cin >> n >> m;
for(int i = 1; i <= m; i++) cin >> p[i];
for(int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i];
//对于每一段路程区间,用差分计算各段路走了多少次
for(int i = 1; i < m; i++)
{
int l = min(p[i], p[i + 1]);
int r = max(p[i], p[i + 1]);
d[l] += 1;
d[r] -= 1;
}
//还原前缀和数组
for(int i = 1; i <= n; i++)
{
s[i] = s[i - 1] + d[i];
}
//对于每一段路,取花费最小的方式
for(int i = 1; i <= n; i++)
{
ans += min(1ll * s[i] * a[i], 1ll * s[i] * b[i] + c[i]);
}
cout << ans;
return 0;
}
标签:前缀,P3406,int,洛谷题,差分,数组,每段 From: https://www.cnblogs.com/jcwy/p/18334552