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

csp信奥赛C高频考点专项训练之贪心算法 --【线性扫描贪心】分糖果题目描述有n nn位小朋友排成一队等待老师分糖果。第i ii位小朋友想要至少a i a_iai​颗糖果并且分给他的糖果数量必须比分给前一位小朋友的糖果数量更多不然他就会不开心。老师想知道至少需要准备多少颗糖果才能让所有小朋友都开心。你能帮帮老师吗输入格式第一行一个正整数n nn表示小朋友的人数。第二行n nn个正整数a 1 , a 2 , … , a n a_1, a_2, \ldots, a_na1​,a2​,…,an​依次表示每位小朋友至少需要的糖果数量。输出格式输出一行一个整数表示最少需要准备的糖果数量。输入输出样例 1输入 14 1 4 3 3输出 116输入输出样例 2输入 215 314 15926 53589793 238462643 383279502 8 8 4 1 9 7 1 6 9 3输出 24508143253说明/提示对于所有测试点保证1 ≤ n ≤ 1000 1 \leq n \leq 10001≤n≤10001 ≤ a i ≤ 10 9 1 \leq a_i \leq 10^91≤ai​≤109。思路分析题目要求为每个小朋友分配糖果数 (c_i)满足c i ≥ a i c_i \ge a_ici​≥ai​至少需要的数量c i c i − 1 c_i c_{i-1}ci​ci−1​严格递增i ≥ 2 i \ge 2i≥2目标是最小化糖果总数∑ c i \sum c_i∑ci​。贪心策略从前往后依次确定每个小朋友的糖果数在满足上述约束的前提下取最小值。第一个小朋友c 1 a 1 c_1 a_1c1​a1​。第 i 个小朋友i ≥ 2 i \ge 2i≥2必须同时满足c i ≥ a i c_i \ge a_ici​≥ai​和c i ≥ c i − 1 1 c_i \ge c_{i-1}1ci​≥ci−1​1因此取c i max ⁡ ( a i , c i − 1 1 ) c_i \max(a_i,\;c_{i-1}1)ci​max(ai​,ci−1​1)。这样得到的序列一定是最优的因为任何更小的分配都会违反某个约束。最终累加所有c i c_ici​即为答案。注意数据范围n ≤ 1000 n \le 1000n≤1000a i ≤ 10 9 a_i \le 10^9ai​≤109总和可能超过 32 位整数范围需使用 64 位整数long long。代码实现#includebits/stdc.husingnamespacestd;intn,a[1005];// n:人数, a:需求数组intmain(){cinn;for(inti0;in;i)cina[i];longlongsa[0],pa[0];// s:总糖果数, p:前一个小朋友的糖果数for(inti1;in;i){longlongcurmax((longlong)a[i],p1);// 当前最少糖果数scur;// 累加pcur;// 更新前一个值}coutsendl;return0;}功能分析输入处理读取小朋友人数 n 和需求数组 a。贪心构造第一个小朋友直接分配a 1 a_1a1​颗糖果。后续每位小朋友分配max ⁡ ( a i , c i − 1 1 ) \max(a_i,\;c_{i-1}1)max(ai​,ci−1​1)颗保证需求与递增约束。累加求和使用long long避免溢出。输出结果打印最少需要的糖果总数。各种学习资料助力大家一站式学习和提升#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;}