csp信奥赛C++高频考点专项训练之贪心算法 --【线性扫描贪心】：积木大赛

csp信奥赛C高频考点专项训练之贪心算法 --【线性扫描贪心】积木大赛题目描述春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为n nn的大厦大厦可以看成由n nn块宽度为1 11的积木组成第i ii块积木的最终高度需要是h i h_ihi​。在搭建开始之前没有任何积木可以看成n nn块高度为0 00的积木。接下来每次操作小朋友们可以选择一段连续区间[ l , r ] [l, r][l,r]然后将第L LL块到第R RR块之间含第L LL块和第R RR块所有积木的高度分别增加1 11。小 M 是个聪明的小朋友她很快想出了建造大厦的最佳策略使得建造所需的操作次数最少。但她不是一个勤于动手的孩子所以想请你帮忙实现这个策略并求出最少的操作次数。输入格式包含两行第一行包含一个整数n nn表示大厦的宽度。第二行包含n nn个整数第i ii个整数为h i h_ihi​。输出格式建造所需的最少操作数。输入输出样例 1输入 15 2 3 4 1 2输出 15说明/提示样例解释其中一种可行的最佳方案依次选择[ 1 , 5 ] [1,5][1,5]$ [1,3] [2,3] [3,3] [5,5]$。数据范围对于30 % 30\%30%的数据有1 ≤ n ≤ 10 1 \leq n \leq 101≤n≤10对于70 % 70\%70%的数据有1 ≤ n ≤ 1000 1 \leq n \leq 10001≤n≤1000对于100 % 100\%100%的数据有1 ≤ n ≤ 100000 1 \leq n \leq 1000001≤n≤1000000 ≤ h i ≤ 10000 0 \leq h_i \leq 100000≤hi​≤10000。思路分析这道题是经典的区间增量操作最小次数问题。核心结论最少操作次数等于所有相邻位置的正向高度差之和即ans ∑ i 1 n max ⁡ ( 0 , h i − h i − 1 ) , 其中 h 0 0 \text{ans} \sum_{i1}^{n} \max(0,\ h_i - h_{i-1}),\quad \text{其中 } h_0 0ans∑i1n​max(0,hi​−hi−1​),其中h0​0证明每次操作可以视为将一个区间整体加1。从第一块积木开始当前高度为0要达到h 1 h_1h1​至少需要h 1 h_1h1​次操作每次操作可以包含第1块。当处理到第i块时如果h i h i − 1 h_i h_{i-1}hi​hi−1​说明必须新增h i − h i − 1 h_i - h_{i-1}hi​−hi−1​次操作来提升这部分高度如果h i ≤ h i − 1 h_i \le h_{i-1}hi​≤hi−1​则前面的操作已经可以覆盖当前积木的增量无需额外操作。因此累加所有正的高度差即得最优解。时间复杂度O(n)空间O(1)。代码实现#includebits/stdc.husingnamespacestd;intmain(){intn,pre0,cur,ans0;cinn;for(inti1;in;i){cincur;if(curpre)anscur-pre;// 正向高度差累加precur;// 更新前一个高度}coutansendl;return0;}功能分析输入处理读取宽度n然后依次读入每个位置的目标高度。核心计算用变量pre记录上一块的高度初始0。每读入当前高度cur若cur pre则将差值累加到答案中。更新pre cur供下一次比较。输出结果打印最少操作次数。正确性验证以样例为例输入52 3 4 1 2i1: cur20 → ans2, pre2i2: cur32 → ans213, pre3i3: cur43 → ans314, pre4i4: cur1≤4 → 不变, pre1i5: cur21 → ans415, pre2输出5各种学习资料助力大家一站式学习和提升#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;}