P13303 [GCJ 2013 Finals] Drummer

在任何乐队中，**鼓手**都扮演着极其重要的角色——负责保持节奏。如果鼓手的节奏不稳定，可能会毁掉整场演出。 你是一支极受欢迎的摇滚乐队的主唱，而你现在遇到了一个小麻烦。你的鼓手刚刚辞职，去做职业电子游戏玩家了。你必须立刻找到新的鼓手。幸运的是，候选人并不缺乏，每个人都想加入你的乐队。你的任务是从中选出节奏最稳定的那个人。 你的计划如下：你会让每个候选人单独试音。在试音时，候选人会用鼓槌敲击鼓面若干次。理想情况下，相邻两次敲击之间的时间间隔应该完全相同，从而形成**完美的节奏**。在完美节奏中，敲击的时间戳应当呈如下等差数列：$T_0$，$T_0 + K$，$T_0 + 2\times K$，$\dots$，$T_0 + (N - 1)\times K$。 当然，在现实生活中，人类几乎不可能打出完全完美的节奏。因此，每个候选人的节奏都会有一个误差 $E$，即每个 $T_i$ 与某个完美节奏的时间戳最多相差 $E$。现在，给定一个候选人的敲击时间序列，请你求出所有可能的完美节奏中，误差 $E$ 的最小值。

第一行为测试用例数 $T$。接下来有 $T$ 个测试用例。每个测试用例包含两行，代表一位候选人的试音。第一行为一个整数 $N$。第二行为 $N$ 个用空格分隔的整数，表示候选人每次敲击的时间戳（单位为毫秒），按递增顺序给出。

对于每个测试用例，输出一行 `"Case #x: E"`，其中 $x$ 为测试用例编号（从 1 开始），$E$ 为所有可能的误差中的最小值。 只要你的答案与正确答案的绝对误差或相对误差不超过 $10^{-6}$，就会被判为正确。

**限制条件** - $1 \leq T \leq 100$ **小数据集（9 分，测试集 1 - 可见）** - 时间限制：~~60~~ 6 秒 - $2 \leq N \leq 10$ - $0 \leq T_i \leq 100$ **大数据集（20 分，测试集 2 - 隐藏）** - 时间限制：~~120~~ 12 秒 - 90% 的测试点满足 $2 \leq N \leq 1000$ - 所有测试点满足 $2 \leq N \leq 50000$ - $0 \leq T_i \leq 10^6$ 翻译由 ChatGPT-4.1 完成。