第 i 位小朋友至少要 aᵢ 颗,且必须比前一位多。求最少要准备多少颗糖果。
有 n 位小朋友排成一队。第 i 位小朋友想要至少 aᵢ 颗糖果,并且分给他的糖果数量必须严格多于前一位小朋友(否则他会不开心)。
老师想知道至少需要准备多少颗糖果才能让所有小朋友都开心。
贪心严格递增递推long long
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n;第二行 n 个正整数 aᵢ |
| 输出 | 最少需要的糖果总数 |
| 数据范围 | 1 ≤ n ≤ 1000 |
| 数值范围 | 1 ≤ aᵢ ≤ 10⁹ |
| 严格性 | bᵢ 必须严格大于 bᵢ₋₁,不能相等 |
我们一个个来,每次都取"刚好满足条件的最小值"。
没有"比前一位多"的限制
所以直接发 a₁
b₁ = 1,累计 1
下限是 4,同时要比 b₁ = 1 大(即至少 2)
max(4, 1 + 1) = max(4, 2) = 4
b₂ = 4,累计 5
下限是 3,但要比 b₂ = 4 大(即至少 5)
max(3, 4 + 1) = max(3, 5) = 5
注意这里自己的下限 3 没起作用,是被前一位抬上去的
b₃ = 5,累计 10
max(3, 5 + 1) = max(3, 6) = 6
b₄ = 6,累计 16
| 小朋友 | 自己的下限 aᵢ | 前一位发的 bᵢ₋₁ | 实际发 bᵢ | 说明 |
|---|---|---|---|---|
| 1 | 1 | — | 1 | 直接取 a₁ |
| 2 | 4 | 1 | 4 | 4 > 1 + 1?不,4 ≥ 2,取下限 4 |
| 3 | 3 | 4 | 5 | 被前一位抬高到 5(下限 3 没起作用) |
| 4 | 3 | 5 | 6 | 被前一位抬高到 6 |
总和 = 1 + 4 + 5 + 6 = 16 ✓
样例 2 的输入里有 383279502 这样的大数字,n 又有 15 位。我们看看实际发糖数会涨到多少。
| 小朋友 | aᵢ | 实际发 bᵢ |
|---|---|---|
| 1 | 314 | 314 |
| 2 | 15926 | 15926 |
| 3 | 53589793 | 53589793 |
| 4 | 238462643 | 238462643 |
| 5 | 383279502 | 383279502 |
| 6 | 8 | 383279503 ← 被前一位抬高! |
| 7 | 8 | 383279504 |
| … | … | 后面每位都比前一位多 1 |
bᵢ = max(aᵢ, bᵢ₋₁ + 1),边算边累加
先确定最后一位实际拿多少,再往前推
| 方案 | 遍历次数 | 核心代码 |
|---|---|---|
| 贪心递推 | 1 次 | 约 6 行 |
| 两次遍历 | 2 次 | 约 12 行 |
输入每位小朋友的下限 aᵢ(空格分隔),程序会算出实际发糖数并给出总数。
点按钮开始 →
#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; }
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 混算时容易出错。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
1 | 5 | 只有一位,直接发下限 |
2 | 3 | 1 + 2,第二位被抬到 2 |
3 | 6 | 1 + 2 + 3,递增抬升 |
3 | 6 | 下限本身已递增,恰好满足 |
4 | 16 | 题面样例 1 |
15 | 4508143253 | 题面样例 2,考察 long long |
max(a₁, 1) 因为 a₁ ≥ 1 恰好等于 a₁。)max(aᵢ, bᵢ₋₁ + 1),不是 max(aᵢ, bᵢ₋₁)。用 prev 滚动记录前一位的糖数,不需要保存整个数组,所以是 O(1)。
✅ n 只有 1000,时间上毫无压力;真正的考点是识别出需要用 long long。
// 递推类题目的通用模板 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 意识 | 先估算结果量级再选类型 | 所有涉及累加、连乘的题目 |