此题实际上是一个模拟问题,要求任意k个连续元素总和不超过sum,那么可以从左到右使用滑动窗口的方式取枚举每k个连续的元素,若超过,则对窗口内最后一位数字进行操作
from collections import deque
n, k, sum_val = map(int, input().split())
a = list(map(int, input().split()))
小红有一个长度为n的数组a,下标从1开始,一个好数组要求任意连续的k个元素的总和不超过sum。
现在可以执行任意次修改,每次修改选择一个下标i(1≤i≤n),令ai=ai−1,注意a不能是负数。
最少执行几次操作,才能使得数组成为一个好数组。
第一行三个整数
n k sum(1≤k≤n≤2×105,1≤sum≤1013),含义和题目描述一致。
第二行包含n个整数ai(0≤ai≤109),表示数组。
输出一行一个整数,表示最少操作次数。
输入
5 3 10
9 7 3 6 5
输出
10
说明
修改为[9,1,0,5,5],只需要操作10次。