GESP 题解库 / 3 级题解 / [GESP202506 三级] 分糖果 · 第 6 / 28 题
GESP202506 三级 · B4359 · 简单

分糖果

第 i 位小朋友至少要 aᵢ 颗,且必须比前一位多。求最少要准备多少颗糖果。

📊
n ≤ 1000
数据规模
🔢
aᵢ ≤ 10⁹
数值范围
⚡
O(n)
时间复杂度
🎯
贪心递推
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

有 n 位小朋友排成一队。第 i 位小朋友想要至少 aᵢ 颗糖果,并且分给他的糖果数量必须严格多于前一位小朋友(否则他会不开心)。

老师想知道至少需要准备多少颗糖果才能让所有小朋友都开心。

💡
人话翻译:给每位小朋友实际发的糖数记作 bᵢ,需要满足两个条件:① bᵢ ≥ aᵢ;② bᵢ > bᵢ₋₁(第一位没有前一位限制)。要使总和最小,每位都应"刚好卡着下限发"。

🔍 关键词提取

贪心严格递增递推long long

已知条件

项目说明
输入第一行 n;第二行 n 个正整数 aᵢ
输出最少需要的糖果总数
数据范围1 ≤ n ≤ 1000
数值范围1 ≤ aᵢ ≤ 10⁹
严格性bᵢ 必须严格大于 bᵢ₋₁,不能相等

需要解决的问题

02
思维导图
整理解题思路的全貌
🍬 每一步都卡下限
📥 读入
n 和数组 a
实际发糖数记作 b
总和用 long long
b 由前一项递推
🧠 递推规则
b₁ = a₁(第一位无约束)
bᵢ ≥ aᵢ(满足自己的要求)
bᵢ > bᵢ₋₁(严格递增)
bᵢ = max(aᵢ, bᵢ₋₁ + 1)
➕ 累加
每算出一个 bᵢ 就加到总和
边算边加,不用存数组
最后输出总和
注意 long long
⚠️ 易错点
写成 bᵢ = max(aᵢ, bᵢ₋₁) 漏了 +1
用 int 导致溢出
总和用 int 累加
把"严格"当成"不小于"
03
样例手算推导
样例 1 逐人推导

🧮 样例 1:[1, 4, 3, 3],答案 16

我们一个个来,每次都取"刚好满足条件的最小值"。

1
第 1 位小朋友(a₁ = 1)

没有"比前一位多"的限制

所以直接发 a₁

b₁ = 1,累计 1

2
第 2 位小朋友(a₂ = 4)

下限是 4,同时要比 b₁ = 1 大(即至少 2)

max(4, 1 + 1) = max(4, 2) = 4

b₂ = 4,累计 5

3
第 3 位小朋友(a₃ = 3)

下限是 3,但要比 b₂ = 4 大(即至少 5)

max(3, 4 + 1) = max(3, 5) = 5

注意这里自己的下限 3 没起作用,是被前一位抬上去的

b₃ = 5,累计 10

4
第 4 位小朋友(a₄ = 3)

max(3, 5 + 1) = max(3, 6) = 6

b₄ = 6,累计 16

📊 逐人结果

小朋友自己的下限 aᵢ前一位发的 bᵢ₋₁实际发 bᵢ说明
11—1直接取 a₁
24144 > 1 + 1?不,4 ≥ 2,取下限 4
3345被前一位抬高到 5(下限 3 没起作用)
4356被前一位抬高到 6

总和 = 1 + 4 + 5 + 6 = 16 ✓

🧮 样例 2:为什么必须用 long long

样例 2 的输入里有 383279502 这样的大数字,n 又有 15 位。我们看看实际发糖数会涨到多少。

小朋友aᵢ实际发 bᵢ
1314314
21592615926
35358979353589793
4238462643238462643
5383279502383279502
68383279503 ← 被前一位抬高!
78383279504
……后面每位都比前一位多 1
🔑
关键观察:第 6 位小朋友只要 8 颗,但前一位发到了 3.8 亿,他必须拿到 3.8 亿 + 1 颗!这种"小数字被大数字抬高"正是本题的核心考点。最终答案 4508143253 已经超过 int 上限(约 21 亿),所以必须用 long long。
04
解法对比
贪心递推 vs 其他思路

⚔️ 解法对比

🟢 贪心递推(推荐) 推荐

bᵢ = max(aᵢ, bᵢ₋₁ + 1),边算边累加

  • 时间复杂度 O(n)
  • 空间 O(1)(不用存数组)
  • 每一步都取最小可行值
  • 代码 6 行核心逻辑
💡
贪心为什么正确:把某一位的糖发多了,后面每一位的"下限门槛"都会跟着抬高,总和只会变大。所以每位都发"刚好够"时总和最小。

🟠 先求最终最大值再倒推

先确定最后一位实际拿多少,再往前推

  • 需要先正着推一遍才知道终值
  • 等于要遍历两次
  • 本质还是同一个递推
  • 没有简化问题
⚠️
结论:这题没有比 O(n) 更快的做法,因为每个 aᵢ 都必须看一遍。贪心一次遍历就是最优解。

📈 性能对比

方案遍历次数核心代码
贪心递推1 次约 6 行
两次遍历2 次约 12 行
05
算法流程图
一次遍历,边算边加
开始读入 n 和数组 a;sum = 0,prev = 0i 从 1 到 ncur = max(aᵢ, prev + 1)sum 累加 cur;prev = curn 位小朋友都发完了吗?输出 sum(long long)结束还有小朋友 → 继续发糖
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🍬 最少糖果计算器

输入每位小朋友的下限 aᵢ(空格分隔),程序会算出实际发糖数并给出总数。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);

    long long sum = 0;      // 总和可能到 10^12,必须 long long
    long long prev = 0;     // 前一位实际拿到的糖果数

    for (int i = 0; i < n; i++) {
        long long a;
        scanf("%lld", &a);
        long long cur = max(a, prev + 1);   // 取"下限"和"比前一位多 1"的较大者
        sum += cur;
        prev = cur;
    }

    printf("%lld\n", sum);
    return 0;
}
🔑
为什么不需要存整个数组?计算 bᵢ 时只用到 bᵢ₋₁,所以用一个变量 prev 滚动更新即可,空间降到 O(1)。这是递推题的常用优化。

📖 关键几行怎么看

代码作用为什么这样写
long long sum累加总数样例 2 的答案 45 亿已超 int 上限
max(a, prev + 1)核心递推兼顾"自己的下限"和"必须比前一位多"
prev = cur更新前一位为下一位提供比较基准
scanf("%lld", &a)读入大整数aᵢ 可达 10⁹,要用 long long 读
⚠️
三个经典错误:① 写成 max(a, prev) 漏掉 +1,违反"严格递增";② 用 int sum 累加,样例 2 直接溢出;③ 把 aᵢ 读成 int,虽然 10⁹ 没超 int,但和 long long 混算时容易出错。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
1
5
5只有一位,直接发下限
2
1 1
31 + 2,第二位被抬到 2
3
1 1 1
61 + 2 + 3,递增抬升
3
1 2 3
6下限本身已递增,恰好满足
4
1 4 3 3
16题面样例 1
15
314 15926 … 3
4508143253题面样例 2,考察 long long
✅
自查清单:① 递推式有没有 +1?② 总和是不是 long long?③ 第一位有没有特殊处理?(其实不用,b₀ = 0 时 max(a₁, 1) 因为 a₁ ≥ 1 恰好等于 a₁。)

🚨 易错点清单

⚠️
漏掉 +1:题目要求"必须比前一位更多",所以递推式是 max(aᵢ, bᵢ₋₁ + 1),不是 max(aᵢ, bᵢ₋₁)。
⚠️
用 int 存总和:样例 2 答案 45 亿已超 int 上限(2147483647),即使 aᵢ 本身没超 int,累加后也会溢出。
⚠️
把 aᵢ 当成 int 读入后与 long long 运算:虽然本题 aᵢ ≤ 10⁹ 恰好能放进 int,但统一用 long long 更安全,也避免类型提升的坑。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n)
空间复杂度
O(1)
n 最大
1000
总和上限
约 10¹²

时间怎么算的?

空间都用在哪?

用 prev 滚动记录前一位的糖数,不需要保存整个数组,所以是 O(1)。

✅ n 只有 1000,时间上毫无压力;真正的考点是识别出需要用 long long。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 递推类题目的通用模板
long long prev = 初始值;
long long ans = 0;
for (int i = 0; i < n; i++) {
    long long cur = 根据 a[i] 和 prev 计算;
    ans += cur;
    prev = cur;          // 滚动更新
}

// 常见递推式对照
// 严格递增:cur = max(a[i], prev + 1)
// 不严格递增(可相等):cur = max(a[i], prev)
// 严格递减:cur = max(a[i], prev - 1)(注意下界)

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
贪心取最小值每位发"刚好够"的糖最小代价分配、资源分配类题目
递推 + 滚动变量只用 prev 记住前一项所有只依赖前一项的递推题
long long 意识先估算结果量级再选类型所有涉及累加、连乘的题目
🌟
思考题:如果把要求从"必须比前一位多"改成"必须比前一位少"(即严格递减),递推式会变成什么?有没有可能无解?(提示:当某位的下限 aᵢ 太大时,就凑不出递减序列了。)