P13229 [GCJ 2015 #3] Smoothing Window

Adamma 是一位对温度感兴趣的气候科学家。她每分钟记录一次当前温度，得到一个整数序列：$x_{1}, x_{2}, \ldots, x_{\mathrm{N}}$。（Adamma 使用自己特殊的温标，而不是常见的摄氏度或开尔文，因此这些值可能很大也可能为负数！）她经常把这些温度绘制在电脑屏幕上。 今天早上，她决定计算这个序列的滑动平均值，以获得更平滑的曲线。她使用了大小为 $\mathbf{K}$ 的平滑窗口，这意味着她将 $\mathbf{N}$ 个温度值转换为 $(\mathbf{N}-\mathbf{K}+1)$ 个平均温度值：$s_{1}, s_{2}, \ldots, s_{\mathbf{N}-\mathbf{K}+1}$。每个 $s_{i}$ 是 $x_{i}, x_{i+1}, \ldots, x_{i+\mathbf{K}-1}$ 的平均值。原始的 $x_{i}$ 都是整数，但 $s_{i}$ 可能是小数。 不幸的是，Adamma 忘记保存原始的温度序列了！现在她想要回答另一个问题——原始序列中最大温度和最小温度的差是多少？换句话说，她需要计算 $\max \left\{x_{1}, \ldots, x_{\mathrm{N}}\right\}-\min \left\{x_{1}, \ldots, x_{\mathrm{N}}\right\}$。但她手头只有 $\mathrm{N}$、$\mathrm{K}$ 和平滑后的序列。 经过一番思考，Adamma 意识到这可能无法唯一确定，因为可能有多种原始序列都能产生相同的平滑序列。在这种情况下，她想知道所有可能的原始序列中，最大温度和最小温度的差的最小值是多少。

输入的第一行为测试用例数 $\mathbf{T}$。接下来有 $\mathbf{T}$ 组测试用例，每组测试用例包含两行。第一行包含两个整数 $\mathrm{N}$ 和 $\mathbf{K}$，用空格分隔。第二行包含整数 $\operatorname{sum}_{1}, \operatorname{sum}_{2}, \ldots, \operatorname{sum}_{\mathrm{N}-\mathbf{K}+1}$，用空格分隔。$s_{i}$ 由 $\operatorname{sum}_{i} / \mathbf{K}$ 给出。

对于每组测试用例，输出一行，格式为 "Case #x: y"，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为最大温度和最小温度的最小可能差值。

**样例解释** 在第 1 组测试用例中，平滑后的序列为： $$0.5, 1.0, 1.5, 2.0, 2.5, 3.0, 3.5, 4.0, 4.5$$ 能够得到最小差值的整数序列为： $$0, 1, 1, 2, 2, 3, 3, 4, 4, 5$$ 注意，序列： $$0.5, 0.5, 1.5, 1.5, 2.5, 2.5, 3.5, 3.5, 4.5, 4.5$$ 虽然也能得到相同的平滑序列且最大差值为 $4$，但这不是有效答案，因为原始温度必须为整数。 在第 2 组测试用例中，我们只知道 $100$ 个原始值的和为 $-100$。所有原始值都为 $-1$ 也是可能的，此时最大最小差为 $0$，这是最小可能的差值。 在第 3 组测试用例中，原始序列可能为： $$-4, 8, -4, 8, -4, 8, -4$$ **数据范围** - $1 \leq \mathrm{T} \leq 100$。 - $2 \leq \mathbf{K} \leq \mathrm{N}$。 - $\operatorname{sum}_{i}$ 为 $-10000$ 到 $10000$ 之间的整数。 **小数据范围（6 分）** - 时间限制：5 秒。 - $2 \leq \mathrm{N} \leq 100$。 **大数据范围（7 分）** - 时间限制：10 秒。 - $2 \leq \mathrm{N} \leq 1000$。 - $2 \leq \mathbf{K} \leq 100$。 由 ChatGPT 4.1 翻译