ZX1024 海底高铁
大约 4 分钟
ZX1024 海底高铁
【算法】 差分、贪心
【C++】 差分数组、前缀和、long long
【难度】 普及/提高−
一、题目简述
一条铁路连接 个城市,共有 段铁路(第 段连接城市 和城市 )。现在知道列车依次经过 个城市 。
对于第 段铁路,有两种购票方式:
- 纸质单程票:每次乘坐花费 元
- IC 卡:先花 元购买该段铁路的 IC 卡,之后每次乘坐只需 元()
求完成整个行程的最少总花费。
数据范围:,。
二、解题思路
2.1 问题转化
关键观察:每段铁路是独立的。对于第 段铁路,只要我们知道了它被经过的次数 ,就可以独立决策是全部买纸质票还是买 IC 卡:
- 全买纸质票:
- 买 IC 卡:
取两者较小值即可。因此问题的核心是统计每段铁路被经过的次数。
2.2 用差分统计经过次数
列车依次经过 。对于相邻两个城市 和 ,列车会经过它们之间的所有铁路段。
假设 (否则交换),那么经过的铁路段是 。例如从城市 2 到城市 5,经过铁路段 2, 3, 4。
这是一个区间加 1 的问题,可以用差分数组 处理:
- 对于每对相邻城市 ,设 ,
cnt[L] += 1,cnt[R] -= 1(注意是 不是 ,因为铁路段编号到 )
最后对 做一次前缀和, 即为第 段铁路被经过的次数。
2.3 贪心决策
对每段铁路 ():
2.4 手动模拟
,,行程序列 。
相邻城市对:
- :,经过铁路段
- :,经过铁路段
- :,经过铁路段
- :,经过铁路段
差分统计:
cnt[1] += 1, cnt[3] -= 1 (1->3)
cnt[2] += 1, cnt[3] -= 1 (3->2)
cnt[2] += 1, cnt[4] -= 1 (2->4)
cnt[2] += 1, cnt[4] -= 1 (4->2)差分数组:
前缀和后:(铁路段 1 经过 1 次,段 2 经过 4 次,段 3 经过 2 次)
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
long long cnt[N]; // 差分数组,统计每段铁路的经过次数
int P[N]; // 行程序列
long long A[N], B[N], C[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int N, M;
cin >> N >> M;
for (int i = 1; i <= M; i++) {
cin >> P[i];
}
// 统计每段铁路的经过次数(差分)
for (int i = 1; i < M; i++) {
int u = P[i], v = P[i + 1];
if (u > v) swap(u, v);
// 经过铁路段 [u, v-1]
cnt[u]++;
cnt[v]--;
}
// 前缀和还原经过次数
for (int i = 1; i < N; i++) {
cnt[i] += cnt[i - 1];
}
// 贪心决策每段铁路的购票方式
long long ans = 0;
for (int i = 1; i < N; i++) {
cin >> A[i] >> B[i] >> C[i];
long long paper = cnt[i] * A[i]; // 全买纸质票
long long ic = C[i] + cnt[i] * B[i]; // 买 IC 卡
ans += min(paper, ic);
}
cout << ans << endl;
return 0;
}四、复杂度分析
- 时间复杂度:。差分统计 ,前缀和 ,贪心决策 。
- 空间复杂度:。需要存储差分数组、行程序列和票价信息。
五、易错点
- 区间方向:统计经过次数时,区间是 (,),差分时
cnt[L]++,cnt[R]--,注意不是cnt[R+1]--。 - 答案可能超 int: 可达 , 可达 ,总花费可达 ,必须使用
long long。 - IC 卡经过 0 次的情况:
min(cnt[i] * A[i], C[i] + cnt[i] * B[i])在 时自动选择纸质票(0 元),不会错误地买卡。 - 铁路段编号:第 段铁路连接城市 和 ,共 段,循环注意边界。
