分数: 1300 点
问题陈述
给你整数 N, K,以及长度-N 非负整数序列 A = (A_1, A_2, \dots, A_N).
A 是单调非递减序列。也就是说, A_i \leq A_{i+1} 适用于所有人 i = 1, 2, \dots, N - 1.
我们称长度为N 非负整数序列 X = (X_1, X_2, \dots, X_N) 一个“好的序列”如果 X 是单调非递减的,可以使 X 等于 0 通过应用以下操作零次或多次:
- 选择一个整数 i 这样 1 \leq i \leq N - K + 1。让 S = X_i + X_{i+1} + \dots + X_{i+K-1}。更换每个 i-th 通过 此时的第 (i+K-1)第一个元素 X 与 \left\lfloor \frac{S}{K} \right\rfloor.
找到最大可能值 \sum_{i=1}^N B_i 用于非负整数序列 B = (B_1, B_2, \dots, B_N) 满足以下所有条件:
- B_i \leq A_i 适用于所有人 i = 1, 2, \dots, N.
- B 是一个单调非递减序列,并且是一个“好序列”。
你有 T 测试用例;解决它们中的每一个。
约束
- 1 \leq T \leq 10^5
- 2 \leq K \leq N \leq 2 \times 10^5
- 0 \leq A_i \leq 10^{9}
- A_i \leq A_{i+1} 适用于所有人 i = 1, 2, \dots, N - 1.
- 所有输入值均为整数。
- 总和 N 一个输入中的所有测试用例最多 2 \times 10^5.
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
每个案例均按以下格式给出:
N K A_1 A_2 \dots A_N
输出
打印 T 行。的 i- 第行应包含以下问题的答案 i- 第一个测试用例。
示例输入 1
4 4 2 0 1 2 3 4 3 0 1 2 3 20 5 1 2 3 3 4 5 6 7 7 8 9 9 11 13 14 16 16 17 18 19 20 10 36410986 135774405 160873759 200077345 386257217 408140905 426675713 448759426 470780343 572969565 653981029 693304642 741916215 764524315 768298046 811893935 840607643 847634785 856942510 883746061
示例输出 1
6 5 185 739
在第一个测试用例中, A 本身就是一个“好的序列”。例如,我们可以将所有元素 A 等于 0 执行以下步骤:
- 让 i=3。然后, S=A_3+A_4=5。更换 A_3 和 A_4 与 \left\lfloor \frac{5}{2} \right\rfloor = 2,导致 A=(0,1,2,2).
- 让 i=2。然后, S=A_2+A_3=3。更换 A_2 和 A_3 与 \left\lfloor \frac{3}{2} \right\rfloor = 1,导致 A=(0,1,1,2).
- 让 i=3。然后, S=A_3+A_4=3。更换 A_3 和 A_4 与 \left\lfloor \frac{3}{2} \right\rfloor = 1,导致 A=(0,1,1,1).
- 让 i=1。然后, S=A_1+A_2=1。更换 A_1 和 A_2 与 \left\lfloor \frac{1}{2} \right\rfloor = 0,导致 A=(0,0,1,1).
- 让 i=2。然后, S=A_2+A_3=1。更换 A_2 和 A_3 与 \left\lfloor \frac{1}{2} \right\rfloor = 0,导致 A=(0,0,0,1).
- 让 i=3。然后, S=A_3+A_4=1。更换 A_3 和 A_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 是一个“好序列”并且满足条件。