csp信奥赛C++高频考点专项训练之贪心算法 --【线性扫描贪心】：铺设道路

csp信奥赛C高频考点专项训练之贪心算法 --【线性扫描贪心】铺设道路题目描述春春是一名道路工程师负责铺设一条长度为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输入 16 4 3 2 5 3 5输出 19说明/提示【样例解释】一种可行的最佳方案是依次选择[ 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 ∑ i 2 n max ⁡ ( 0 , d i − d i − 1 ) d_1 \sum_{i2}^{n} \max(0, d_i - d_{i-1})d1​∑i2n​max(0,di​−di−1​)。原理从左到右扫描如果当前深度大于前一个深度说明需要额外增加若干次操作来覆盖这一段凸起的高度否则可以延续之前的操作区间。这个算法时间复杂度 O(n)空间复杂度 O(n)。代码实现#includebits/stdc.husingnamespacestd;intmain(){intn;//道路长度cinn;inta[n];//存储每个区域的深度for(inti0;in;i)cina[i];longlongansa[0];//初始化答案为第一块深度for(inti1;in;i)if(a[i]a[i-1])ansa[i]-a[i-1];//累加正差值coutansendl;return0;}功能分析输入处理读取道路长度n和每个区域的初始下陷深度a[i]。核心计算将第一个区域的深度作为初始操作次数。从第二个区域开始若当前深度大于前一个深度则将差值累加到答案中。该累加过程等价于统计所有“上升段”的高度和。输出结果打印最少需要的天数。各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;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标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新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 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}