小A的糖果

题意

给定 n 个糖果盒，第 i 个盒子里有 a_i 颗糖。每次可以从某个盒子里吃掉一颗糖，要求最后任意相邻两个盒子的糖果数之和都不超过 x。问最少要吃掉多少颗糖。

思路

朴素做法是枚举每个盒子最后剩多少颗糖，然后检查所有相邻对是否合法，保留总糖数最大的方案：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53// brute.cpp：小数据暴力解，枚举每个盒子最终剩多少颗糖。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

int n;
long long x;
long long a[MAXN], b[MAXN];
long long total_sum;
long long best_keep;
long long suffix_sum[MAXN];

void dfs(int pos, long long keep_sum) {
    if (keep_sum + suffix_sum[pos] <= best_keep) {
        return;
    }

    if (pos > n) {
        best_keep = max(best_keep, keep_sum);
        return;
    }

    // 暴力枚举第 pos 个盒子最终剩下多少颗糖。
    for (long long remain = 0; remain <= a[pos]; remain++) {
        if (pos > 1 && b[pos - 1] + remain > x) {
            continue;
        }
        b[pos] = remain;
        dfs(pos + 1, keep_sum + remain);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> x;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        total_sum += a[i];
    }
    for (int i = n; i >= 1; i--) {
        suffix_sum[i] = suffix_sum[i + 1] + a[i];
    }

    best_keep = -1;
    dfs(1, 0);

    cout << total_sum - best_keep << '\n';

    return 0;
}

正解从左到右处理。假设已经处理完 0..i-1，现在只需要让 a[i-1] + a[i] <= x。

如果这一对超过了 x，必须吃掉 a[i-1] + a[i] - x 颗。优先从当前盒子 a[i] 里吃更好，因为左边盒子已经参与过上一对限制；减少右边不会破坏左边已经合法的部分，还会让后面的相邻对更容易合法。

所以扫描每一对：

计算超出量 extra = a[i-1] + a[i] - x；
若 extra <= 0，不处理；
优先从 a[i] 中吃掉 extra；
如果当前盒不够，再补吃 a[i-1]。

Python 知识

sys.stdin.buffer.read().split() 适合读取大量整数。
列表 candies 可以原地修改，直接保存贪心处理后的盒子数量。
continue 可以让“不超标”的分支尽早结束，主逻辑更清楚。

C++ 里常写数组和 long long；Python 的 int 不会溢出，本题只需要注意用线性扫描避免超时。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28import sys


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n, x = data[0], data[1]
    candies = data[2:2 + n]

    answer = 0
    for i in range(1, n):
        extra = candies[i - 1] + candies[i] - x
        if extra <= 0:
            continue

        eat = min(extra, candies[i])
        candies[i] -= eat
        answer += eat

        extra -= eat
        if extra > 0:
            candies[i - 1] -= extra
            answer += extra

    print(answer)


if __name__ == "__main__":
    main()

复杂度

只扫描一遍数组，时间复杂度是 $O(n)$ 。

空间复杂度是 $O(n)$ ，如果不计输入数组就是 $O(1)$ 。

总结

这题的核心是“从左到右固定已经处理好的部分”。当前相邻对超标时，优先减少右边盒子，避免回头影响左侧。

目录

题意

思路

Python 知识

代码

复杂度

总结