C++实现P3817糖果贪心算法详解及代码优化

## 🔍 问题分析 **P3817** 是洛谷（Luogu）上的一道经典**递推/动态规划**题目，题目全名为《小A的糖果》。题意大致是： > 有 n 个盒子排成一行，每个盒子中有若干个糖果。小A每次可以拿走任意一个盒子中的任意数量糖果，目标是使**任意相邻两个盒子中的糖果总数不超过 x**。求最少需要拿走的糖果数。 ### 📌 输入格式 - 第一行：两个整数 n 和 x - 第二行：n 个整数 a₁, a₂, …, aₙ ### 📌 输出格式 - 一个整数，表示最少拿走的糖果总数 --- ## 💡 核心思路 这是一道**贪心（Greedy）** 问题，而非动态规划。关键观察： - 我们**从左到右**扫描每个相邻对 `(a[i], a[i+1])`。 - 当 `a[i] + a[i+1] > x` 时，必须从这两个盒子中拿走至少 `sum - x` 颗糖果。 - **贪心策略**：每次**优先从右侧盒子拿走**，因为右侧盒子还会与下一个盒子相邻，减少右侧糖果有助于解决后续冲突，而左侧已经处理完毕不再影响。 ### 🧠 贪心正确性证明（简要） - 当处理到位置 i 时，前面的相邻对都已满足条件，当前只影响 `(i, i+1)` 和 `(i+1, i+2)`。 - 若从左侧拿，只解决当前冲突；若从右侧拿，还能减少后面的冲突概率，因此**从右侧拿总是更优或至少不差**。 --- ## 📝 C++ 代码实现 ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n, x; cin >> n >> x; vector<long long> a(n); // 使用 long long 防止溢出 for (int i = 0; i < n; i++) cin >> a[i]; long long ans = 0; // 总拿走数量 for (int i = 0; i < n - 1; i++) { long long sum = a[i] + a[i + 1]; if (sum > x) { long long need = sum - x; // 需要拿走的数量 ans += need; // 优先从右侧拿，右侧最多能拿 need 颗 if (a[i + 1] >= need) { a[i + 1] -= need; } else { // 右侧不够，剩余从左侧拿（但实际不会出现，因为左侧此时已满足） a[i] -= (need - a[i + 1]); a[i + 1] = 0; } } } cout << ans << endl; return 0; } ``` ### 📖 代码逐段解释 | 部分 | 说明 | |------|------| | `vector<long long> a(n)` | 使用 `long long` 避免累加溢出（n 可达 1e5，x 可达 1e9） | | `for (int i = 0; i < n - 1; i++)` | 遍历所有相邻对 | | `sum = a[i] + a[i+1]` | 计算当前相邻总和 | | `need = sum - x` | 需拿走的糖果数 | | 优先从右侧拿 | 更新 `a[i+1]`，若不够再扣左侧 | --- ## ⚠️ 常见陷阱与优化建议 1. **溢出问题**：`a[i] + a[i+1]` 可能超过 int 范围，**必须使用 `long long`**。 2. **边界条件**：n=1 时循环不会执行，直接输出 0，代码自然处理。 3. **贪心策略的正确性**：一定要理解“从右侧拿”的原因，否则容易写成从左侧拿导致 WA。 4. **时间复杂度**：O(n) 线性扫描，非常高效。 5. **空间优化**：可以不用 vector，直接边读边处理（但需要保存上一个值），代码可进一步简化。 ### 🚀 优化版（不存数组） ```cpp #include <iostream> using namespace std; int main() { long long n, x; cin >> n >> x; long long prev, curr; cin >> prev; // 读入第一个 long long ans = 0; for (int i = 1; i < n; i++) { cin >> curr; long long sum = prev + curr; if (sum > x) { long long need = sum - x; ans += need; // 从右侧拿 curr -= need; if (curr < 0) curr = 0; // 不会发生，但防御 } prev = curr; // 更新为新的右侧值 } cout << ans << endl; return 0; } ``` --- ## 🎯 类似题目推荐 - **P1090** 合并果子（贪心+优先队列） - **P1208** 混合牛奶（简单贪心） - **P3818** 小A的糖果（扩展版） --- ## 💎 开发建议 - 写题时先**手动模拟小数据**验证贪心策略，再上机。 - 养成使用 `long long` 的习惯，尤其涉及累加或乘积。 - 代码尽量清晰，注释关键逻辑，有助于调试和复查。 ######[AI写代码神器 | 1259点数解答 | 2026-08-30 13:03:58]