csp信奥赛C++高频考点专项训练之前缀和&差分 --【一维差分】：海底高铁

题目描述

该铁路经过N NN个城市，每个城市都有一个站。不过，由于各个城市之间不能协调好，于是乘车每经过两个相邻的城市之间（方向不限），必须单独购买这一小段的车票。第i ii段铁路连接了城市i ii和城市i + 1 ( 1 ≤ i < N ) i+1(1\leq i<N)i+1(1≤i<N)。如果搭乘的比较远，需要购买多张车票。第i ii段铁路购买纸质单程票需要A i A_iAi​博艾元。

虽然一些事情没有协调好，各段铁路公司也为了方便乘客，推出了 IC 卡。对于第i ii段铁路，需要花C i C_iCi​博艾元的工本费购买一张 IC 卡，然后乘坐这段铁路一次就只要扣B i ( B i < A i ) B_i(B_i<A_i)Bi​(Bi​<Ai​)元。IC 卡可以提前购买，有钱就可以从网上买得到，而不需要亲自去对应的城市购买。工本费不能退，也不能购买车票。每张卡都可以充值任意数额。对于第i ii段铁路的 IC 卡，无法乘坐别的铁路的车。

Uim 现在需要出差，要去M MM个城市，从城市P 1 P_1P1​出发分别按照P 1 , P 2 , P 3 , ⋯ , P M P_1,P_2,P_3,\cdots,P_MP1​,P2​,P3​,⋯,PM​的顺序访问各个城市，可能会多次访问一个城市，且相邻访问的城市位置不一定相邻，而且不会是同一个城市。

现在他希望知道，出差结束后，至少会花掉多少的钱，包括购买纸质车票、买卡和充值的总费用。

输入格式

第一行两个整数，N , M N,MN,M。

接下来一行，M MM个数字，表示P i P_iPi​。

接下来N − 1 N-1N−1行，表示第i ii段铁路的A i , B i , C i A_i,B_i,C_iAi​,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 22到3 33以及8 88到9 99买票，其余买卡。

对于30 % 30\%30%数据M = 2 M=2M=2。

对于另外30 % 30\%30%数据N ≤ 1000 N\leq1000N≤1000，M ≤ 1000 M\leq1000M≤1000。

对于100 % 100\%100%的数据M , N ≤ 10 5 M,N\leq 10^5M,N≤105，A i , B i , C i ≤ 10 5 A_i,B_i,C_i\le10^5Ai​,Bi​,Ci​≤105。

思路分析

题目要求计算在给定行程下，为每一段铁路选择购卡或单程票的最小总花费。
关键步骤：

1. 统计每段铁路被经过的次数：
   • 给定城市序列 (P 1 , P 2 , … , P M P_1, P_2, \dots, P_MP1​,P2​,…,PM​)，相邻两次访问 (P j P_jPj​) 到 (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)。
2. 对第 (i) 段铁路，两种方案花费为：
   • 全单程票：(k i × A i k_i \times A_iki​×Ai​)
   • 买卡：(C i + k i × B i C_i + k_i \times B_iCi​+ki​×Bi​)（因为B i < A i B_i < A_iBi​<Ai​，购卡后每次花费更少）
     取较小值累加即得答案。
3. 注意数据范围，使用long long避免溢出。

代码实现

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;intmain(){intn,m;scanf("%d%d",&n,&m);// n:城市数,m:访问次数vector<int>p(m);// 访问序列for(inti=0;i<m;++i)scanf("%d",&p[i]);vector<ll>d(n+2,0);// 差分数组,1~n-1有效for(inti=0;i<m-1;++i){// 处理每对相邻城市inta=p[i],b=p[i+1];intl=min(a,b),r=max(a,b)-1;// 经过的铁路区间if(l<=r){// 区间非空d[l]+=1;// 差分左端点+1d[r+1]-=1;// 右端点后一位-1}}ll cnt=0,ans=0;// cnt:当前铁路累计次数for(inti=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);return0;}

功能分析

1. 差分统计经过次数：利用d[l] += 1, d[r+1] -= 1在 O(1) 时间内标记区间，最后前缀和得到每条铁路的真实经过次数，时间复杂度 O(N+M)。
2. 逐段决策：对每条铁路，比较全单程票总价与买卡并充值总价，选择较小者累加。
3. 空间优化：只使用两个数组（访问序列 p 和差分数组 d），d 大小 N+2，满足10 5 10^5105数据范围。

【完整系列请查看专栏】：
信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

【秘籍汇总】（完整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>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}