相邻的糖果

[编程题]相邻的糖果

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有n个盒子摆成一排，每个盒子内都有a_i个糖果。
现在你可以执行以下操作：
·你可以选择任意一个盒子，在选择的盒子内吃掉一个糖果。
对你的要求如下：
·任何m个相邻的盒子内糖果数量不能超过x个。
请问，实现要求的最少操作次数是多少？

输入描述:

第一行三个数字n, m, x(2 ≤ n,m ≤ 10⁶,1 ≤ x ≤ 10⁹)。
第二行n个数字(1 ≤ a_i ≤ 10⁹)。

输出描述:

输出一个操作数，代表实现要求的最少操作数。

示例1

输入

3 2 3
2 1 2

输出

说明

2 1 2满足题目要求，任意相邻的两个数值之和均不超过3，所以不需要进行任何操作。

算法知识视频讲解

Turgen

发表于 2026-02-07 01:25:44

如果把每组m个元素看成一个分区，我们的分区示意图如下：可以明显看到：每个m元素的分区，削减最后一个元素，可以让影响后续m个分区，使它们的负担变小，因此我们的贪心策略是：每次优先删除一个分区的最后几个元素，因为这样可以帮助后续几个分区的总和一起减小。在实现上，维护一个变量s，用来表示当前窗口的值，每次展开全文