【题目来源】
洛谷：P3406 海底高铁 - 洛谷
【题目描述】
该铁路经过 \(N\) 个城市，每个城市都有一个站。不过，由于各个城市之间不能协调好，于是乘车每经过两个相邻的城市之间（方向不限），必须单独购买这一小段的车票。第 \(i\) 段铁路连接了城市 \(i\) 和城市 \(i+1(1\le i\lt N)\)。如果搭乘的比较远，需要购买多张车票。第 \(i\) 段铁路购买纸质单程票需要 \(A_i\) 博艾元。
虽然一些事情没有协调好，各段铁路公司也为了方便乘客，推出了 IC 卡。对于第 \(i\) 段铁路，需要花 \(C_i\) 博艾元的工本费购买一张 IC 卡，然后乘坐这段铁路一次就只要扣 \(B_i(B_i\lt A_i)\) 元。IC 卡可以提前购买，有钱就可以从网上买得到，而不需要亲自去对应的城市购买。工本费不能退，也不能购买车票。每张卡都可以充值任意数额。对于第 \(i\) 段铁路的 IC 卡，无法乘坐别的铁路的车。
Uim 现在需要出差，要去 \(M\) 个城市，从城市 \(P_1\) 出发分别按照 \(P_1,P_2,P_3,\dots,P_M\) 的顺序访问各个城市，可能会多次访问一个城市，且相邻访问的城市位置不一定相邻，而且不会是同一个城市。
现在他希望知道，出差结束后，至少会花掉多少的钱，包括购买纸质车票、买卡和充值的总费用。
【输入】
第一行两个整数，\(N,M\)。
接下来一行，\(M\) 个数字，表示 \(P_i\)。
接下来 \(N−1\) 行，表示第 \(i\) 段铁路的 \(A_i,B_i,C_i\)。
【输出】
一个整数，表示最少花费
【输入样例】
9 10
3 1 4 1 5 9 2 6 5 3
200 100 50
300 299 100
500 200 500
345 234 123
100 50 100
600 100 1
450 400 80
2 1 10
【输出样例】
6394
【解题思路】
【算法标签】
《洛谷 P3406 海底高铁》 #前缀和#
【代码详解】
#include <bits/stdc++.h>
using namespace std;#define int long long // 定义int为long long类型
const int N = 100005; // 定义最大数组长度int a[N], b[N], c[N]; // a: 差分数组, b: 存储站点序列, c: 前缀和数组
int n, m, x, y, z, ans; // n: 站点数, m: 访问次数, x,y,z: 临时变量, ans: 总花费signed main() // 使用signed替代int，因为定义了int为long long
{// 输入站点数量和访问次数cin >> n >> m;// 输入访问的站点序列for (int i = 1; i <= m; i++) {cin >> b[i];// 从第二次访问开始处理if (i > 1) {// 确定相邻两个站点的顺序（从小到大）if (b[i] > b[i - 1]) {x = b[i - 1], y = b[i];}else {x = b[i], y = b[i - 1];}// 使用差分数组标记区间（左闭右开）a[x + 1]++;a[y + 1]--;}}// 计算前缀和，得到每个区间的访问次数for (int i = 1; i <= n; i++) {c[i] = c[i - 1] + a[i];}// 注释掉的调试输出// for (int i=1; i<=n; i++) {// cout << c[i] << " ";// }// cout << endl;// 计算最小总花费for (int i = 2; i <= n; i++) {cin >> x >> y >> z;// 比较纸质票和IC卡的总花费，取较小值ans += min(x * c[i], y * c[i] + z);}// 输出最终结果cout << ans;return 0;
}
【运行结果】
9 10
3 1 4 1 5 9 2 6 5 3
200 100 50
300 299 100
500 200 500
345 234 123
100 50 100
600 100 1
450 400 80
2 1 10
6394