P14908 [NHSPC 2024] 花果山

【部分不宜展示的内容已被删除】 「我们必须立刻改变！从现在起，花果山所有桃树结下的桃子，直接接收后，再重新分配给花果山上的猴子，直到所有猴子都拥有等量的桃子为止！」 孙悟空要求统计所有猴子所拥有的桃子以及桃树每天的桃子产量。花果山统计局很快地将相关数据呈给孙悟空：花果山上总共有 $n$ 只猴子，第 $i$ 只猴子拥有 $a_i$ 颗桃子，而桃树的产量很稳定，每天都能够生产出 $k$ 颗桃子。 花果山的内政大臣天命人针对重新分配的方法，向孙悟空提出建言：「为了花果山上的和谐，重新分配桃子时，不可以从猴子手中夺走任何桃子。每天接收到的桃子，必须当天就分配出去。最重要的是要避免相对剥夺感，每一天分配到最多桃子的猴子，只能比分配到最少桃子的猴子多得一颗桃子。」孙悟空觉得很有道理，便要求按照天命人的建议进行分配。 假设 $n=4,k=7,a_1=1,a_2=2,a_3=3,a_4=4$，即花果山上总共有 4 只猴子，分别有 1, 2, 3, 4 颗桃子，而桃树每天的产量是 7 颗桃子。按照天命人的建议，每只猴子每天都可以分配到一颗或是两颗桃子，不能更少也不能更多，否则会带来相对剥夺感。此时可以通过下列步骤，让所有的猴子拥有等量的桃子： 1. 第一天到第三天都分配各两颗桃子给前三只猴子、一颗桃子给第四只猴子。三天过后，四只猴子分别拥有 7, 8, 9, 7 颗桃子。 2. 第四天、第五天都分配各两颗桃子给前两只猴子、一颗桃子给第三只猴子、两颗桃子给第四只猴子。五天过后，四只猴子分别拥有 11, 12, 11, 11 颗桃子。 3. 第六天分配一颗桃子给第二只猴子、各两颗桃子给其余的三只猴子。六天过后，四只猴子分别拥有 13, 13, 13, 13 颗桃子，数量相等。 请撰写一个程序计算，最少要几天之后，才能使得所有的猴子都拥有等量的桃子。

$$\begin{aligned} &T \\ &\text{testcase}_1 \\ &\text{testcase}_2 \\ &\vdots \\ &\text{testcase}_T \end{aligned}$$ - $T$ 表示测试数据个数。 - $\text{testcase}_i$ 为第 $i$ 笔测试资料。 每一笔测试资料的输入格式如下 $$\begin{aligned} &n \ k \\ &a_1 \ a_2 \ \ldots \ a_n \end{aligned}$$ - $n$ 为猴子的数量。 - $k$ 为桃子每天的产量。 - $a_i$ 代表第 $i$ 只猴子拥有的桃子数量。

输出 $T$ 笔测试资料之答案 $$\begin{aligned} &\text{answer}_1 \\ &\text{answer}_2 \\ &\vdots \\ &\text{answer}_T \end{aligned}$$ - $\text{answer}_i$ 为第 $i$ 笔测试资料之答案。 每一笔测试资料答案的输出格式如下：如该组测试资料在 $x$ 天后，所有猴子能够拥有等量的桃子，则输出一个整数 $x$，如果那天永远不可能到来，则输出 `poor monkeys`。

### 数据限制 - $1 \leq T \leq 5 \times 10^5$。 - $2 \leq n \leq 10^6$。 - $1 \leq k \leq 10^9$。 - $0 \leq a_i \leq 10^9$。 - $a_1 \leq a_2 \leq \dots \leq a_n$ 且 $a_1 < a_n$。 - 输入的数皆为整数。 - $T$ 笔测试资料中 $n$ 的总和 $\sum n \leq 10^6$。 ### 评分说明 本题共有五组子任务，条件限制如下所示。 每一组可有一或多笔测试资料，该组所有测试资料皆需答对才会获得该组分数。 | 子任务 | 分数 | 额外输入限制 | | :------: | :----: | ------------ | | 1 | 2 | $\sum n \leq 100$，$k = 1$，$a_i \leq 100$ 且保证最少天数存在。 | | 2 | 3 | $\sum n \leq 100$，$k = n-1$，$a_i \leq 100$ 且保证最少天数存在。 | | 3 | 29 | $\sum n \leq 1000$，$k \leq 1000$，$a_i \leq 1000$ 且保证若最少天数存在，则不超过 $10^4$。 | | 4 | 39 | $\sum n \leq 10^5$，$k \leq 10^5$，$a_i \leq 10^5$，见注 2。 | | 5 | 27 | 无额外限制。 | - 注 1：「最少天数存在」的意思是有一天所有猴子可以拥有等量的桃子，不存在的意思则是这一天永远不可能到来。 - 注 2：子任务 4 保证对于那些最少天数存在的测试资料，最少天数的总和不超过 $10^5$。换句话说，正确答案中输出的数字总和不超过 $10^5$。