P4793 糖果问题（基础）

解题思路

1. 读懂题目：有 N 个糖果盒排成一排，第 i 盒有 aᵢ 颗糖。要求任意两个相邻盒子里的糖加起来不超过 x 颗。小 A 每次只能从一盒里吃掉一颗，问最少吃掉多少颗才能满足要求。

2. 打个比方：就像一排小桶装糖，规定"邻居两桶加起来不能超过限额"。哪两桶超标了，就从中舀走一些糖，直到每一对邻居都不超。

3. 贪心策略：从左到右，依次检查每一对相邻的盒子。如果 a[i] 和 a[i+1] 加起来大于 x，就必须要吃掉 (a[i]+a[i+1]-x) 颗，一颗都不能少。

4. 优先从右边吃：这多出来的糖尽量从"右边的盒子"里吃。为什么呢？因为右边这盒还要和它右边的 a[i+2] 配对，先把右边这盒减下来，后面的约束就更容易满足，总的吃糖数就不会浪费。如果右边这盒的糖不够减（它本身很少），剩下的再从左边那盒吃。

5. 为什么从左到右扫一遍就够：处理完 (a[i-1], a[i]) 这一对后，前面的条件已经满足。之后我们只可能减少 a[i] 或 a[i+1]，减少只会让"前面已经处理过的相邻对"的和更小，绝不会破坏前面的结果，所以不用回头。

6. 看例子：样例 1,6,1,2,0,4，x=1。第 1 对 1+6=7，多吃 6 颗（把 6 减成 0）；第 2 对 0+1=1，不超；第 3 对 1+2=3，吃 2 颗（2 变 0）；第 4 对 0+0=0，不超；第 5 对 0+4=4，吃 3 颗（4 变 1）。一共 6+2+3=11 颗。

7. 边界情况：如果某一盒糖特别多，比如 x=1 而一盒有 6 颗，它和任何邻居加起来都超过 1，必须被吃掉很多。处理到包含它的相邻对时，算法自然会把多余的糖减掉。注意减的时候先减右边、右边不够再减左边，保证不会减出负数。

参考代码

// P4793 糖果问题：从左到右检查相邻两盒，和超过 x 先减右边、不够再减左边，保证最少
#include <iostream>
using namespace std;
int candyBox[105];  // 每盒糖果的数量

int main() {
    int N, x;
    cin >> N >> x;
    for (int i = 0; i < N; i++) cin >> candyBox[i];
    int eatTotal = 0;  // 总共吃掉的糖果颗数
    // 从左到右检查每一对相邻的盒子
    for (int i = 0; i < N - 1; i++) {
        int pairSum = candyBox[i] + candyBox[i + 1];  // 相邻两盒糖果之和
        if (pairSum > x) {
            int needEat = pairSum - x;  // 这两盒至少得吃掉的数量
            // 优先从右边这盒吃，因为右边还影响后面一对；右边不够再从左边吃
            int eatRight = needEat < candyBox[i + 1] ? needEat : candyBox[i + 1];
            candyBox[i + 1] -= eatRight;
            candyBox[i] -= (needEat - eatRight);
            eatTotal += needEat;
        }
    }
    cout << eatTotal << endl;
    return 0;
}

复杂度分析

整个算法只需要从左到右扫一遍盒子，每对盒子只计算一次，时间是 O(N)，N≤100，几乎是瞬间完成。空间上只用一个长度为 105 的数组，是 O(N)。这是典型的"线性扫描"贪心，非常高效。