← 返回题目列表

Codeforces · 1622/C

C. 设置或减少

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

给你一个整数数组 $$$a_1, a_2, \dots, a_n$$$ 和整数 $$$k$$$。

只需一步,您就可以

- 选择某个索引 $$$i$$$ 并将 $$$a_i$$$ 减一(使 $$$a_i = a_i - 1$$$);
- 或选择两个索引 $$$i$$$ 和 $$$j$$$ 并将 $$$a_i$$$ 设置为等于 $$$a_j$$$ (使 $$$a_i = a_j$$$)。

计算数组 $$$\sum\limits_{i=1}^{n}{a_i} \le k$$$ 的总和所需的最少步骤是多少? (允许将数组的值设为负数)。

输入

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

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le 10^{15}$$$) - 数组 $$$a$$$ 的大小及其总和的上限。

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

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

输出

对于每个测试用例,打印一个整数 - 使 $$$\sum\limits_{i=1}^{n}{a_i} \le k$$$ 的最小步骤数。

示例

输入 #1

4
1 10
20
2 69
6 9
7 8
1 2 1 3 1 2 1
10 1
1 2 3 1 2 6 1 6 8 10

输出 #1

10
0
2
7

注意

在第一个测试用例中,您应该减少 $$$a_1$$$ $$$10$$$ 次,以使总和低于或等于 $$$k = 10$$$。

在第二个测试用例中,数组 $$$a$$$ 的总和已经小于或等于 $$$69$$$,因此不需要更改它。

在第三个测试用例中,您可以例如:

1. 设置$$$a_4 = a_3 = 1$$$;
2. $$$a_4$$$减1,得到$$$a_4 = 0$$$。

在第四个测试用例中,您可以例如:

1.选择$$$a_7$$$并减少$$$3$$$倍;你会得到 $$$a_7 = -2$$$;
2. 选择$$$4$$$元素$$$a_6$$$、$$$a_8$$$、$$$a_9$$$和$$$a_{10}$$$并且它们等于$$$a_7 = -2$$$。