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

输入 1

4 1 4 3 3

输出 1

16

输入输出样例 2

输入 2

15 314 15926 53589793 238462643 383279502 8 8 4 1 9 7 1 6 9 3

输出 2

4508143253

说明/提示

对于所有测试点，保证1 ≤ n ≤ 1000 1 \leq n \leq 10001≤n≤1000，1 ≤ 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≤1000，a i ≤ 10 9 a_i \le 10^9ai​≤109，总和可能超过 32 位整数范围，需使用 64 位整数（long long）。

代码实现

#include<bits/stdc++.h>usingnamespacestd;intn,a[1005];// n:人数, a:需求数组intmain(){cin>>n;for(inti=0;i<n;i++)cin>>a[i];longlongs=a[0],p=a[0];// s:总糖果数, p:前一个小朋友的糖果数for(inti=1;i<n;++i){longlongcur=max((longlong)a[i],p+1);// 当前最少糖果数s+=cur;// 累加p=cur;// 更新前一个值}cout<<s<<endl;return0;}

功能分析

1. 输入处理：读取小朋友人数 n 和需求数组 a。
2. 贪心构造：
   • 第一个小朋友直接分配a 1 a_1a1​颗糖果。
   • 后续每位小朋友分配max ⁡ ( a i , c i − 1 + 1 ) \max(a_i,\;c_{i-1}+1)max(ai​,ci−1​+1)颗，保证需求与递增约束。
3. 累加求和：使用long long避免溢出。
4. 输出结果：打印最少需要的糖果总数。

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

#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信奥赛冲刺一等奖有效刷题题解：

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 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}