P3817 小A的糖果 (贪心)

传送门

思路：

首先我们可以把这几个糖果盒分对来讨论； 先从第一个糖果盒和第二个开始； 如果一个糖果盒的数量就超限了，我们当然至少要把它吃到剩下x个； 然后如果单论两个都没有超限，但加起来超限了怎么办呢？ 首先第一个糖果盒是只有一个分组的（和第二个）， 而第二个糖果盒却有两个分组（和第1个/和第3个）； 所以如果我们吃掉第一个里的，只会减少一个分组的量，而如果吃掉第二个里的，可以减少2个分组的量。所以我们要尽量吃掉第二个里的糖果。 处理好第一个分组后，来看第二个，因为第一个分组已经被处理好了，所以可以无视它，然后问题又变成了前一个问题。 以此类推就好了。

参考代码：

using ll = long long;
 
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, x;
    std::cin >> n >> x;
    ll sum{};
    std::vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    if (a[0] > x) {
        sum += a[0] - x;
        a[0] = x;
    }
    for (int i = 1; i < n; i++) {
        if (a[i] + a[i - 1] > x) {
            sum += a[i] + a[i - 1] - x;
            if (a[i] >= (x - a[i] - a[i - 1])) {
                a[i] -= a[i] + a[i - 1] - x;
            } else {
                a[i - 1] -= (a[i] + a[i - 1] - x) - a[i];
                a[i] = 0;
            }
        }
    }
    std::cout << sum;
    return 0;
}