GESP2025年6月认证C++三级( 第三部分编程题（2、分糖果）

《分糖果王国大冒险》 一、故事背景1、在“甜甜王国”里小朋友们排成一队 2、每个小朋友都有一个愿望 “我至少要这么多糖”同时还有一个超级重要的规则后面的同学必须比前面的糖多3、否则就会 哭 二、题目规则1、给你一个数组a[i] 第i个小朋友至少要的糖果数2、你要分糖✔ 每个人 ≥ 自己的要求✔ 每个人 前一个人求最少需要多少糖果 三、举个例子一步一步讲1、输入4 1 4 3 32、分给小朋友 第1步第1个小朋友要 ≥1 → 给 1当前[1] 第2步第2个小朋友要求≥4 且 前一个(1)最小就是max(4, 11) 4当前[1, 4] 第3步第3个小朋友要求≥3 且 前一个(4)必须超过4max(3, 41) 5当前[1, 4, 5] 第4步第4个小朋友要求≥3 且 前一个(5)结果max(3, 51) 6当前[1, 4, 5, 6]3、最后答案1 4 5 6 16 四、核心思想每一步都做一件事当前 max(自己的需求, 前一个 1)这是“贪心算法” 五、再来一个例子1、输入5 2 2 2 2 22、过程第1个2 第2个max(2,21)3 第3个max(2,31)4 第4个max(2,41)5 第5个max(2,51)63、答案23456 20 六、完整代码#include iostream using namespace std; int main() { int n; cin n; int a[1005]; for(int i 1; i n; i) { cin a[i]; } long long sum a[1]; // 第一个人 for(int i 2; i n; i) { // 核心满足两个条件 if(a[i] a[i-1]) { a[i] a[i-1] 1; } sum a[i]; } cout sum endl; return 0; } 七、代码升级版a[i] max(a[i], a[i-1] 1); 八、总结口诀前一个是台阶 后一个要更高 不够就往上加 刚好最省糖 九、为什么这是“最少”因为我们每一步只加“刚刚够用”的糖没有多给一颗 十、一句话总结每个人都比前一个多1同时满足自己的最低要求