CF1814D Balancing Weapons

你在一家开发在线射击游戏的游戏工作室找到了工作，你的第一个重要任务是帮助平衡武器。游戏中有 $n$ 把武器：第 $i$ 把枪有一个整数射速 $f_i$ 和每发子弹的整数伤害 $d_i$。第 $i$ 把枪的总火力等于 $p_i = f_i \cdot d_i$。 你需要修改某些枪的 $d_i$ 的值，使得新的 $d_i$ 仍然是整数，并且所有枪的火力都变得平衡。给定一个整数 $k$，如果满足 $ \max\limits_{1 \le i \le n}{p_i} - \min\limits_{1 \le i \le n}{p_i} \le k $，则称这些枪是平衡的。 由于玩家不喜欢大的改动，你需要尽量少地修改 $d_i$ 的值。你需要求出最少需要修改多少把枪的 $d_i$，才能使所有枪达到平衡？ 注意，新的 $d_i$ 必须是大于 $0$ 的整数。

第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$2 \le n \le 3000$，$0 \le k \le 1500$），分别表示需要平衡的枪的数量和允许的最大火力差。 第二行包含 $n$ 个整数 $f_1, f_2, \dots, f_n$（$1 \le f_i \le 2000$），表示第 $i$ 把枪的射速。 第三行包含 $n$ 个整数 $d_1, d_2, \dots, d_n$（$1 \le d_i \le 10^9$），表示第 $i$ 把枪每发子弹的伤害。 保证所有测试用例中 $n$ 的总和不超过 $3000$。

对于每个测试用例，输出一个整数，表示最少需要修改多少把枪的 $d_i$，才能使所有枪达到平衡。 注意，新的 $d_i$ 必须是大于 $0$ 的整数。

在第一个测试用例中，你可以将 $d_1 = 2$，$d_2 = 4$。这样得到 $d = [2, 4, 1, 2]$，火力值为 $p = [12, 12, 13, 14]$。这些枪是平衡的，因为 $14 - 12 \le 2$。 在第二个测试用例中，你需要修改所有三把枪的 $d_i$。例如，你可以设置 $d = [5151, 5100, 5050]$。 在第三个测试用例中，所有枪已经是平衡的，因此不需要修改任何一把枪。 由 ChatGPT 4.1 翻译