CF2068C.Ads

提高+/省选-

通过率：0%

AC君温馨提醒

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

你在热门平台 YooCube 的观看列表中有 $n$ 个视频。第 $i$ 个视频时长为 $d_i$ 分钟。

YooCube 近期增加了广告投放频率。广告仅会在视频之间播放。当完成一个视频后，若满足以下任一条件则会播放广告：

你需要按任意顺序观看这 $n$ 个视频。假设你刚刚观看完一个广告，且视频结束后无需再观看广告。求在最优观看顺序下，你被迫观看的广告数量的最小值。

每个测试包含多个测试用例。第一行包含整数 $t$ （ $1 \leq t \leq 100\,000$ ）——测试用例数量。接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k$ （ $1 \leq n \leq 100\,000$ ， $1 \leq k \leq 30\,000$ ）——观看列表中的视频数量及触发广告的时间参数。

第二行包含 $n$ 个整数 $d_1, d_2, \ldots, d_n$ （ $1 \leq d_i \leq 10\,000$ ）——各视频的时长。

所有测试用例的 $n$ 之和不超过 $10^6$ 。

对于每个测试用例，输出需要观看的广告数量的最小值。

输入#1

5
8 25
4 5 18 3 17 17 18 14
7 21
20 14 1 4 20 8 4
8 1
20 5 9 4 14 12 2 20
8 37
2 13 13 11 12 19 16 18
4 38
15 3 14 7

输出#1

第一个测试用例中，一种可能的观看顺序为 $4, 1, 8, 2, 5, 6, 7, 3$ （对应时长为 $3, 4, 14, 5, 17, 17, 18, 18$ ）。此顺序下，在前三个视频后需要观看一次广告，随后三个视频后需再观看一次广告。注意观看完所有视频后无需观看广告。

翻译由 DeepSeek R1 完成

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