CF2128A.Recycling Center

入门

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

在回收中心，有 $n$ 个垃圾袋，第 $i$ 个垃圾袋的重量为 $a_i$ 。每一秒钟，会依次发生以下两个操作：

你需要花费的最少硬币数是多少，才能销毁所有垃圾袋？

每个测试点包含多组测试数据。第一行包含测试用例数 $t$ （ $1 \le t \le 1000$ ）。接下来是每组测试数据的描述。

每组测试数据的第一行包含两个整数 $n$ 和 $c$ （ $1 \leq n \leq 30$ ， $1 \leq c \leq 10^9$ ）。

每组测试数据的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ （ $1 \leq a_i \leq 10^9$ ），表示每个垃圾袋的重量。

对于每组测试数据，输出一个整数，表示销毁所有垃圾袋所需的最少硬币数。

输入#1

4
5 10
10 4 15 1 8
3 42
1000000000 1000000000 1000000000
10 30
29 25 2 12 15 42 14 6 16 9
10 1000000
1 1 1 1 1 1 1 1 1 864026633

输出#1

在下面的解释中：

对于第一个测试用例，一种方案如下：

$[10, 4, 15, 1, 8]$
$[\color{blue}{10}, 8, 30, 2, 16]$ ， $10$ 被免费销毁，因为 $10 \leq 10$ 。
$[\color{blue}{10}, \color{blue}{8}, 60, 4, 32]$ ， $8$ 被免费销毁，因为 $8 \leq 10$ 。
$[\color{blue}{10}, \color{blue}{8}, 120, 8, \color{red}{32}]$ ， $32$ 被花费 $1$ 个硬币销毁，因为 $32 > 10$ 。
$[\color{blue}{10}, \color{blue}{8}, 240, \color{blue}{8}, \color{red}{32}]$ ， $8$ 被免费销毁，因为 $8 \leq 10$ 。
$[\color{blue}{10}, \color{blue}{8}, \color{red}{240}, \color{blue}{8}, \color{red}{32}]$ ， $240$ 被花费 $1$ 个硬币销毁，因为 $240 > 10$ 。

总共花费了 $2$ 个硬币，并且可以证明这是最优的。

对于第二个测试用例，一种方案如下：

$[1\,000\,000\,000, 1\,000\,000\,000, 1\,000\,000\,000]$
$[\color{red}{1\,000\,000\,000}, 2\,000\,000\,000, 2\,000\,000\,000]$ ， $1\,000\,000\,000$ 被花费 $1$ 个硬币销毁，因为 $1\,000\,000\,000 > 42$ 。
$[\color{red}{1\,000\,000\,000}, \color{red}{2\,000\,000\,000}, 4\,000\,000\,000]$ ， $2\,000\,000\,000$ 被花费 $1$ 个硬币销毁，因为 $2\,000\,000\,000 > 42$ 。
$[\color{red}{1\,000\,000\,000}, \color{red}{2\,000\,000\,000}, \color{red}{4\,000\,000\,000}]$ ， $4\,000\,000\,000$ 被花费 $1$ 个硬币销毁，因为 $4\,000\,000\,000 > 42$ 。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?