csp信奥赛C++高频考点专项训练之前缀和&差分 --【一维差分】：[NOIP 2018 提高组] 铺设道路
题目描述
春春是一名道路工程师，负责铺设一条长度为n nn的道路。
铺设道路的主要工作是填平下陷的地表。整段道路可以看作是n nn块连续的区域，一开始，第i ii块区域下陷的深度为d i d_idi。
春春每天可以选择一段连续区间[ L , R ] [L,R][L,R]，填充这段区间中的每块区域，让其下陷深度减少1 11。在选择区间时，需要保证，区间内的每块区域在填充前下陷深度均不为0 00。
春春希望你能帮他设计一种方案，可以在最短的时间内将整段道路的下陷深度都变为0 00。
输入格式
输入文件包含两行，第一行包含一个整数n nn，表示道路的长度。 第二行包含n nn个整数，相邻两数间用一个空格隔开，第i ii个整数为d i d_idi。
输出格式
输出文件仅包含一个整数，即最少需要多少天才能完成任务。
输入输出样例 1
输入 1
6 4 3 2 5 3 5输出 1
9说明/提示
【样例解释】
一种可行的最佳方案是，依次选择：
[ 1 , 6 ] [1,6][1,6]、[ 1 , 6 ] [1,6][1,6]、[ 1 , 2 ] [1,2][1,2]、[ 1 , 1 ] [1,1][1,1]、[ 4 , 6 ] [4,6][4,6]、[ 4 , 4 ] [4,4][4,4]、[ 4 , 4 ] [4,4][4,4]、[ 6 , 6 ] [6,6][6,6]、[ 6 , 6 ] [6,6][6,6]。
【数据规模与约定】
对于30 % 30\%30%的数据，1 ≤ n ≤ 10 1 ≤ n ≤ 101≤n≤10；
对于70 % 70\%70%的数据，1 ≤ n ≤ 1000 1 ≤ n ≤ 10001≤n≤1000；
对于100 % 100\%100%的数据，1 ≤ n ≤ 100000 , 0 ≤ d i ≤ 10000 1 ≤ n ≤ 100000 , 0 ≤ d_i ≤ 100001≤n≤100000,0≤di≤10000。
思路分析
这个问题等价于：给定一个正整数序列，每次操作可以将一个连续子区间内的所有数减1（区间内所有数必须大于0），问最少操作次数。
经典解法：考虑差分思想。设初始数组为d[1…n]，补一个d[0]=0。从左到右扫描，如果当前深度d[i] > d[i-1]，则说明需要额外进行(d[i] - d[i-1])次操作来覆盖这段“凸起”，因为这些操作无法被前一个位置的区间覆盖。总操作数即为所有正差值的累加和。
例如样例：4 3 2 5 3 5，计算差值：4-0=4，3-4=-1，2-3=-1，5-2=3，3-5=-2，5-3=2，累加正数部分：4+3+2=9，与答案一致。
代码实现
#include<bits/stdc++.h>usingnamespacestd;intmain(){intn,a,b=0,ans=0;// b记录上一个深度，初始0cin>>n;for(inti=1;i<=n;i++){cin>>a;// 当前深度if(a>b)ans+=a-b;// 正差值累加b=a;}cout<<ans<<endl;return0;}功能分析
- 时间复杂度：O(n)，只需一次线性扫描。
- 空间复杂度：O(1)，仅使用几个整型变量。
- 正确性：基于贪心思想，每次操作尽可能向右延伸，统计新增的“台阶”高度。
【完整系列请查看专栏】：
信奥赛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;}
