U619344 eating cows?(标准版) 题解

形式化题目意思

给定一个长度为

n

的序列

a

，你可以对一个长度为

2 \times k+1

的区间加一，这称为一次操作。请问你至少进行几次操作，可以满足

\min ^n_1 a_i \le m

。

采用贪心算法，遍历

a

，如果对于

a_i

这个元素，如果其小于

m

则让

[i,i+2k]

这个区间都加一即可。对于区间修改，单点查询的操作你可以用以下数据结构或预处理方法维护：前缀和差分（题解代码的方法）、树状数组、线段树……

CPP

for(i,1~n) 输入a_i，预处理差分数组 d.
for(i,1~n){
    处理差分数组
    如果 a_i 小于m{
        给 [i,i+2k] 这个区间经行加 l 操作(l为要加多少次才能使 a_i 满足条件)
    }
}
输出方法数