解题思路
本题要求在连续窗口里最大化向下取整后的平均值，窗口长度至少为 w。
- 设答案为整数 x。因为班均是 ⌊sum/len⌋，可行的 x 一定落在 [minvp, maxvp] 里。
- 判定「是否存在长度 ≥w 的窗口，使得 ⌊sum/len⌋≥x」。x 是整数且长度为正，这等价于 sum≥x⋅len，也就是 ∑(vp−x)≥0。
- 令 bp=vp−x，问题变成：是否存在一段长度至少为 w 的子数组，和为非负。用前缀和 pre，窗口 (q,s] 的和是 pres−preq−1。要找某个 s≥w，使得 pres 减去 pre0,…,pres−w 里的最小值 ≥0。
- 从左到右扫右端点，维护前面那段前缀的最小值即可，判定是 O(m)。
- 对 x 二分最大化，共 O(logV) 次判定，V 不超过 2×109。
题目内容
推理集群连续跑了 m 个班次，第 p 个班次的净值记为 vp（可以为负，表示当班调度损耗）。要在班次序列上截取一段连续窗口 [q,s]，窗口长度必须至少为 w，否则调度系统不认这段窗口。
窗口的班均净值定义为
⌊s−q+1vq+vq+1+⋯+vs⌋
其中 ⌊⋅⌋ 表示不超过该实数的最大整数，例如 ⌊−11/2⌋=⌊−5.5⌋=−6。
请在所有长度合法的窗口里，把班均净值做到最大，并输出这个最大值。保证 w≤m，因此至少存在一个合法窗口。
输入描述
首行给出整数 g（1≤g≤10），表示随后有多少组数据。
每一组的格式如下：
该组开头给出整数 m（1≤m≤105），即班次个数。
下一行给出整数 w（1≤w≤m），即窗口最短长度。
第三行 m 个整数 v1,v2,…,vm（∣vp∣≤109），用逗号分隔，依次为各班次净值。
输出描述
输出一行，包含 g 个整数，相邻两项以空格分隔，依次为每一组的最大班均净值。
样例1
输入
3
6
2
4,-1,8,-6,3,5
3
2
-2,-9,-4
4
4
10,-1,-1,10
输出
4 -5 4
说明
第一组最短长度为 2，取最后两个班次 {3,5}，和为 8，班均为 ⌊8/2⌋=4。更长的窗口都到不了 4。
第二组全是亏损。取整段 {−2,−9,−4}，和为 −15，班均为 ⌊−15/3⌋=−5。只取 {−2,−9} 得到 ⌊−11/2⌋=−6，更差。
第三组最短长度等于班次数，只能取整段，和为 18，班均为 ⌊18/4⌋=4。
