2324. 贪吃小 A 的糖果平衡术
1000ms
256MB
简单
贪心算法
题目描述
小 A 有 $N$ 个糖果盒，第 $i$ 个盒中有 $a_i$ 颗糖果。
小 A 每次可以从其中一盒糖果中吃掉一颗。他想知道，要让任意两个相邻的盒子中加起来都只有 $x$ 颗或以下的糖果，至少得吃掉几颗糖。
输入格式
- 第一行包含两个整数 $N$ 和 $x$ ($0 \lt N, x \le 100$)。
- 第二行包含 $N$ 个整数 $a_i$ ($0 \lt a_i \le 100$)。
输出格式
- 输出一个整数，表示至少要吃掉的糖果数量。
样例 1
输入 (Input)
6 1 1 6 1 2 0 4
输出 (Output)
11
样例说明
- **样例解释**：
目标是相邻两盒之和 $\le 1$。
- 盒子序列为 `1 6 1 2 0 4`。
- 处理 `1 6`：和为 7，需吃掉 6 颗（从第二个盒子里吃），变为 `1 0 1 2 0 4`。
- 处理 `0 1`：和为 1，不吃。
- 处理 `1 2`：和为 3，需吃掉 2 颗（从第四个盒子里吃），变为 `1 0 1 0 0 4`。
- 处理 `0 0`：和为 0，不吃。
- 处理 `0 4`：和为 4，需吃掉 3 颗（从第六个盒子里吃），变为 `1 0 1 0 0 1`。
- 总共吃掉：$6 + 2 + 3 = 11$ 颗。
- $0 \lt N, x \le 100$
- $0 \lt a_i \le 100$
这是一个**贪心算法**问题。为了让吃掉的糖果对后续影响最大，当我们发现相邻的两个盒子 $a_i$ 和 $a_{i+1}$ 之和超过 $x$ 时，我们应该**优先从后面的盒子 $a_{i+1}$ 中吃糖**。因为 $a_{i+1}$ 还会参与到与 $a_{i+2}$ 的求和中，吃掉它的糖可以同时减小两组相邻和。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功