AT_agc071_d [AGC071D] Level K Terms

[problemUrl]: https://atcoder.jp/contests/agc071/tasks/agc071_d 给定整数 $N, K$ 和长度为 $N$ 的非负整数序列 $A = (A_1, A_2, \dots, A_N)$。 $A$ 是单调非递减序列，即对于所有 $i = 1, 2, \dots, N-1$，满足 $A_i \leq A_{i+1}$。 对于一个长度为 $N$ 的单调非递减非负整数序列 $X = (X_1, X_2, \dots, X_N)$，如果可以通过以下操作（进行 $0$ 次或多次）使得 $X$ 的所有项变为 $0$，则称 $X$ 为「好序列」： - 选择满足 $1 \leq i \leq N-K+1$ 的整数 $i$，令 $S = X_i + X_{i+1} + \dots + X_{i+K-1}$，将 $X$ 的第 $i, i+1, \dots, i+K-1$ 项的值全部替换为 $\left\lfloor \frac{S}{K} \right\rfloor$。 请找出满足以下所有条件的非负整数序列 $B = (B_1, B_2, \dots, B_N)$ 的 $\sum_{i=1}^N B_i$ 的最大值： - 对于所有 $i = 1, 2, \dots, N$，有 $B_i \leq A_i$； - $B$ 是单调非递减序列且是「好序列」。 给定 $T$ 个测试用例，请对每个用例输出答案。

输入从标准输入按以下格式给出： > $T$ > $\mathrm{case}_1$ > $\vdots$ > $\mathrm{case}_T$ 每个测试用例的格式如下： > $N$ $K$ > $A_1$ $A_2$ $\dots$ $A_N$

输出 $T$ 行。第 $i$ 行对应第 $i$ 个测试用例的答案。

### 约束条件 - $1 \leq T \leq 10^5$ - $2 \leq K \leq N \leq 2 \times 10^5$ - $0 \leq A_i \leq 10^9$ - 对于所有 $i = 1, 2, \dots, N-1$，有 $A_i \leq A_{i+1}$ - 输入中的所有值均为整数 - 单个输入文件中所有测试用例的 $N$ 总和不超过 $2 \times 10^5$ ### 样例解释 #1 对于第一个测试用例，$A$ 本身是「好序列」。例如，通过以下步骤可将所有项变为 $0$： 1. 选择 $i=3$，计算 $S = A_3 + A_4 = 5$，将第 $3, 4$ 项替换为 $\left\lfloor \frac{5}{2} \right\rfloor = 2$，得到 $A = (0, 1, 2, 2)$。 2. 选择 $i=2$，计算 $S = A_2 + A_3 = 3$，将第 $2, 3$ 项替换为 $\left\lfloor \frac{3}{2} \right\rfloor = 1$，得到 $A = (0, 1, 1, 2)$。 3. 选择 $i=3$，计算 $S = A_3 + A_4 = 3$，将第 $3, 4$ 项替换为 $\left\lfloor \frac{3}{2} \right\rfloor = 1$，得到 $A = (0, 1, 1, 1)$。 4. 选择 $i=1$，计算 $S = A_1 + A_2 = 1$，将第 $1, 2$ 项替换为 $\left\lfloor \frac{1}{2} \right\rfloor = 0$，得到 $A = (0, 0, 1, 1)$。 5. 选择 $i=2$，计算 $S = A_2 + A_3 = 1$，将第 $2, 3$ 项替换为 $\left\lfloor \frac{1}{2} \right\rfloor = 0$，得到 $A = (0, 0, 0, 1)$。 6. 选择 $i=3$，计算 $S = A_3 + A_4 = 1$，将第 $3, 4$ 项替换为 $\left\lfloor \frac{1}{2} \right\rfloor = 0$，得到 $A = (0, 0, 0, 0)$。 因此，取 $B = A$ 可得到最大值 $0 + 1 + 2 + 3 = 6$。 对于第二个测试用例，$A$ 不是「好序列」。取 $B = (0, 0, 2, 3)$ 时 $B$ 是「好序列」且满足条件。 翻译由 DeepSeek R1 完成