← 返回题目列表

Codeforces · 1706/D1

D1. 切胡萝卜(简单版)

中文机器翻译题面 查看原题

这是问题的简单版本。版本之间的唯一区别是 $$$n$$$、$$$k$$$、$$$a_i$$$ 的约束以及所有测试用例的 $$$n$$$ 总和。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。

注意异常的内存限制。

给定一个整数数组 $$$a_1、a_2、\ldots、a_n$$$,长度为 $$$n$$$,以及一个整数 $$$k$$$。

长度为 $$$n$$$ 的整数数组 $$$p_1, p_2, \ldots, p_n$$$ 的成本为 $$$$$$\max\limits_{1 \le i \le n}\left(\left \lfloor \frac{a_i}{p_i} \right \rfloor \right) - \min\limits_{1 \le i \le n}\left(\left \lfloor \frac{a_i}{p_i} \right \rfloor \right).$$$$$$

这里,$$$\lfloor \frac{x}{y} \rfloor$$$表示$$$x$$$除以$$$y$$$的整数部分。求数组 $$$p$$$ 的最小成本,使得 $$$1 \le p_i \le k$$$ 对于所有 $$$1 \le i \le n$$$ 而言。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n, k \le 3000$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_1 \le a_2 \le \ldots \le a_n \le 3000$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3000$$$。

输出

对于每个测试用例,打印一个整数 - 满足上述条件的数组 $$$p$$$ 的最小可能成本。

示例

输入 #1

7
5 2
4 5 6 8 11
5 12
4 5 6 8 11
3 1
2 9 15
7 3
2 3 5 5 6 9 10
6 56
54 286 527 1436 2450 2681
3 95
16 340 2241
2 2
1 3

输出 #1

2
0
13
1
4
7
0

注意

在第一个测试用例中,最佳数组是 $$$p = [1, 1, 1, 2, 2]$$$。 $$$\lfloor \frac{a_i}{p_i} \rfloor$$$ 的值数组为 $$$[4, 5, 6, 4, 5]$$$。 $$$p$$$ 的成本为 $$$\max\limits_{1 \le i \le n}(\lfloor \frac{a_i}{p_i} \rfloor) - \min\limits_{1 \le i \le n}(\lfloor \frac{a_i}{p_i} \rfloor) = 6 - 4 = 2$$$。我们可以证明不存在成本更小的数组(满足语句中的条件)。

在第二个测试用例中,最佳数组之一是 $$$p = [12, 12, 12, 12, 12]$$$,这导致所有 $$$\lfloor \frac{a_i}{p_i} \rfloor$$$ 均为 $$$0$$$。

在第三个测试用例中,唯一可能的数组是 $$$p = [1, 1, 1]$$$。