思路

  此题实际上是一个模拟问题，要求任意k个连续元素总和不超过sum，那么可以从左到右使用滑动窗口的方式取枚举每k个连续的元素，若超过，则对窗口内最后一位数字进行操作

代码

python

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)$，令$a_i=a_i-1$，注意$a$不能是负数。

最少执行几次操作，才能使得数组成为一个好数组。

输入描述

第一行三个整数

$n$ $k$ $sum(1≤k≤n≤2×10^5, 1≤sum≤10^{13})$，含义和题目描述一致。

第二行包含$n$个整数$a_i(0≤a_i≤10^9)$，表示数组。

输出描述

输出一行一个整数，表示最少操作次数。

样例1

输入

5 3 10
9 7 3 6 5

输出

10

说明

修改为$[9,1,0,5,5]$，只需要操作$10$次。