U619344 eating cows?(标准版) 题解

· · 题解

形式化题目意思

给定一个长度为 n 的序列 a，你可以对一个长度为 2 \times k+1 的区间加一，这称为一次操作。请问你至少进行几次操作，可以满足 m \le \min ^n_1 a_i。

题目思路

采用贪心算法，遍历 a，如果对于 a_i 这个元素，如果其小于 m 则让 [i,i+2k] 这个区间都加一即可。对于区间修改，单点查询的操作你可以用以下数据结构或预处理方法维护：前缀和差分（题解代码的方法）、树状数组、线段树……

伪代码(不给出AC代码)

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