← 返回题目列表

Codeforces · 2141/D

D. 避免最低限度

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

给定一个整数数组 $$$a_1, a_2, a_3, \dots, a_n$$$。您的任务是使 $$$a$$$ 的所有元素相等。为此,您最多可以执行以下操作 $$$k$$$ 次:

  • 选择从 $$$1$$$ 到 $$$n$$$ 的任意索引 $$$i$$$ 并将 $$$a_i$$$ 加一。
您可以选择数组的任何元素,但如果选择的 $$$a_i$$$ 是 严格大于 比 当前 数组中的最小值,您将获得一枚硬币。

在所有可能的使数组相等的方法中,您最多可以获得多少枚金币?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。接下来是 $$$t$$$ 案例(所有案例都是独立的)。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 3 \cdot 10^5$$$; $$$1 \le k \le 10^{12}$$$) - 数组 $$$a$$$ 的大小以及可以执行的最大操作数。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) - 数组本身。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,如果不可能使所有元素相等,则打印 $$$-1$$$。否则,打印在使所有元素相等的情况下您可以赚取的最大硬币数量。

示例

输入
复制

4
3 16
1 10 2
4 20
6 2 4 9
5 9
7 7 7 7 7
2 1000000000000
1000000000 1000000000

输出
复制

-1
11
0
499999999999

注意

在第一个测试用例中,您至少需要 $$$17$$$ 操作才能使所有元素相等(或获取数组 $$$[10, 10, 10]$$$)。

在第二个测试用例中,例如,您可以将 $$$a_3 = 4$$$ 增加到 $$$10$$$,然后将 $$$a_1 = 6$$$ 增加到 $$$10$$$,之后将 $$$a_4 = 9$$$ 增加到 $$$10$$$,最后将 $$$a_2 = 2$$$ 增加到$$$10$$$。您将执行 $$$19$$$ 操作并总共赚取 $$$(10 - 4) + (10 - 6) + (10 - 9) = 11$$$ 硬币,因为将 $$$a_2$$$ 从 $$$2$$$ 增加到 $$$10$$$ 不会给您任何硬币。

在第三个测试用例中,您可以保持数组不变或使所有元素等于 $$$8$$$ — 两种策略都会给您 $$$0$$$ 硬币。