题面描述

给定一个数组，你可以对任意正整数进行减一操作，目标是使得所有长度为 (x) 的子数组的和不超过 (y)。输入包括数组的长度 (n)、子数组长度 (x)、限制值 (y) 以及数组本身，输出最少需要的操作次数。通过示例可知，合理修改数组中的元素可实现目标，有时可能无需任何操作。

思路：贪心

从前往后依次枚举每个长度为$m$的区间，如果当前区间和不满足条件，按照贪心的思想考虑，则应该优先减少当前区间的最后一个元素，这样可以使得后面区间操作次数少一些。

题解

题目描述

给定一个数组$a_1,a_2,a_3,...,a_n$ ， 你每次可以对数组任意一个正整数进行-1操作。问最少多少次使得其所有长度为$x$的子数组的和 $\leq$ $y$。

输入描述

第一行，两个整数 $x , y(1\leq x \leq 10,0\leq y\leq 1000)$

第二行输入一个整数 $n (1 \leq n \leq 1e5)$，代表数组的大小。

第三行输入 $n$ 个非负整数表示数组 $a$ ，第 $i$ 个数为 $a_i(0 \leq a_i\leq 10^5)$ 。

输出描述

一个整数，代表最少操作次数。

样例

输入

2 4
4
1 3 3 3

输出

2

一种方案是最终改成:1 3 1 3 , 把第三个位置的数从3改成1。花费两次操作

输入

2 6
4
1 3 3 3

输出

0

所有长度为2的子数组([1,3],[3,3],[3,3])的和都小于等于6,所以无需操作