csp信奥赛C++高频考点专项训练之前缀和&差分 –【一维差分】：海底高铁
题目描述
该铁路经过
N
N
N 个城市，每个城市都有一个站。不过，由于各个城市之间不能协调好，于是乘车每经过两个相邻的城市之间（方向不限），必须单独购买这一小段的车票。第
i
i
i 段铁路连接了城市
i
i
i 和城市
i
+
1
(
1
≤
i
<
N
)
i+1(1\\leq i<N)
i+1(1≤i<N)。如果搭乘的比较远，需要购买多张车票。第
i
i
i 段铁路购买纸质单程票需要
A
i
A_i
Ai 博艾元。
虽然一些事情没有协调好，各段铁路公司也为了方便乘客，推出了 IC 卡。对于第
i
i
i 段铁路，需要花
C
i
C_i
Ci 博艾元的工本费购买一张 IC 卡，然后乘坐这段铁路一次就只要扣
B
i
(
B
i
<
A
i
)
B_i(B_i<A_i)
Bi(Bi<Ai) 元。IC 卡可以提前购买，有钱就可以从网上买得到，而不需要亲自去对应的城市购买。工本费不能退，也不能购买车票。每张卡都可以充值任意数额。对于第
i
i
i 段铁路的 IC 卡，无法乘坐别的铁路的车。
Uim 现在需要出差，要去
M
M
M 个城市，从城市
P
1
P_1
P1 出发分别按照
P
1
,
P
2
,
P
3
,
⋯
,
P
M
P_1,P_2,P_3,\\cdots,P_M
P1,P2,P3,⋯,PM 的顺序访问各个城市，可能会多次访问一个城市，且相邻访问的城市位置不一定相邻，而且不会是同一个城市。
现在他希望知道，出差结束后，至少会花掉多少的钱，包括购买纸质车票、买卡和充值的总费用。
输入格式
第一行两个整数，
N
,
M
N,M
N,M。
接下来一行，
M
M
M 个数字，表示
P
i
P_i
Pi。
接下来
N
−
1
N-1
N−1 行，表示第
i
i
i 段铁路的
A
i
,
B
i
,
C
i
A_i,B_i,C_i
Ai,Bi,Ci。
输出格式
一个整数，表示最少花费。
输入输出样例 1
输入 1
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
输出 1
6394
说明/提示
2
2
2 到
3
3
3 以及
8
8
8 到
9
9
9 买票，其余买卡。
对于
30
%
30\\%
30% 数据
M
=
2
M=2
M=2。
对于另外
30
%
30\\%
30% 数据
N
≤
1000
N\\leq1000
N≤1000，
M
≤
1000
M\\leq1000
M≤1000。
对于
100
%
100\\%
100% 的数据
M
,
N
≤
10
5
M,N\\leq 10^5
M,N≤105，
A
i
,
B
i
,
C
i
≤
10
5
A_i,B_i,C_i\\le10^5
Ai,Bi,Ci≤105。
思路分析
题目要求计算在给定行程下，为每一段铁路选择购卡或单程票的最小总花费。 关键步骤：
- 给定城市序列 (
P
1
,
P
2
,
…
,
P
M
P_1, P_2, \\dots, P_M
P1,P2,…,PM)，相邻两次访问 (P
j
P_j
Pj) 到 (P
j
+
1
P_{j+1}
Pj+1) 经过的区间为 ([
min
(
P
j
,
P
j
+
1
)
,
max
(
P
j
,
P
j
+
1
)
−
1
]
[\\min(P_j,P_{j+1}), \\max(P_j,P_{j+1})-1]
[min(Pj,Pj+1),max(Pj,Pj+1)−1])。 - 使用差分数组 (d) 对每个区间加 (1)，最后前缀和得到每段铁路的经过次数 (k_i)。
- 全单程票：(
k
i
×
A
i
k_i \\times A_i
ki×Ai) - 买卡：(
C
i
+
k
i
×
B
i
C_i + k_i \\times B_i
Ci+ki×Bi)（因为B
i
<
A
i
B_i < A_i
Bi<Ai，购卡后每次花费更少） 取较小值累加即得答案。
代码实现
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int n, m; scanf("%d%d", &n, &m); // n:城市数,m:访问次数
vector<int> p(m); // 访问序列
for (int i=0; i<m; ++i) scanf("%d", &p[i]);
vector<ll> d(n+2, 0); // 差分数组,1~n-1有效
for (int i=0; i<m–1; ++i) { // 处理每对相邻城市
int a = p[i], b = p[i+1];
int l = min(a,b), r = max(a,b)–1; // 经过的铁路区间
if (l <= r) { // 区间非空
d[l] += 1; // 差分左端点+1
d[r+1] -= 1; // 右端点后一位-1
}
}
ll cnt = 0, ans = 0; // cnt:当前铁路累计次数
for (int i=1; i<n; ++i) { // 遍历1~n-1段铁路
cnt += d[i]; // 前缀和得到经过次数
ll a, b, c; scanf("%lld%lld%lld", &a, &b, &c);
ans += min(cnt * a, c + cnt * b); // 取较小花费
}
printf("%lld\\n", ans);
return 0;
}
功能分析
10
5
10^5
105数据范围。
【完整系列请查看专栏】： 信奥赛C++普及组CSP-J一等奖通关刷题题单及题解： https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"########## 一站式掌握信奥赛知识! ##########";
cout<<"############# 冲刺信奥赛拿奖! #############";
cout<<"###### 课程购买后永久学习，不受限制! ######";
return 0;
}
【秘籍汇总】（完整csp信奥赛C++学习资料）：
1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：
https://edu.csdn.net/lecturer/7901 点击跳转
2、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转 
https://edu.csdn.net/course/detail/41081 点击跳转 
3、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划： https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL： https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践： https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转
4、csp信奥赛冲刺一等奖有效刷题题解：
信奥赛C++普及组CSP-J一等奖通关刷题题单及题解： https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
信奥赛C+普及高组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）： https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转
5、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）： https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"跟着王老师一起学习信奥赛C++";
cout<<" 成就更好的自己！ ";
cout<<" csp信奥赛一等奖属于你! ";
return 0;
}
