QOJ.ac

QOJ

时间限制: 1 s 内存限制: 512 MB 总分: 100 可 Hack ✓

#17346. 注册

统计

ICPC 2026 长安邀请赛即将开始。有 $n$ 支队伍计划报名参赛,其中第 $i$ 支队伍将在第 $v_i$ 秒访问报名网站。

对于每个正整数 $s$:

  • 如果第 $s$ 秒访问报名网站的队伍数量不超过 $x$,则在第 $s$ 秒访问的所有队伍均成功报名。
  • 否则,报名网站在这一秒会因为访问人数过多而崩溃,所有在第 $s$ 秒访问的队伍都将报名失败。

作为 ICPC 2026 长安邀请赛的总裁判长,Yuki 想要了解本次比赛的报名情况。因此,你需要帮助她计算成功报名的队伍数量。

输入格式

本题包含多个测试用例。

第一行包含一个正整数 $t$ ($1 \le t \le 10^5$),表示测试用例的数量。

对于每个测试用例:

  • 第一行包含两个正整数 $n, x$ ($1 \le n \le 2 \cdot 10^5, 1 \le x \le n$)。
  • 第二行包含 $n$ 个正整数 $v_1, \dots, v_n$ ($1 \le v_i \le 10^9$)。

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

输出格式

对于每个测试用例,输出一行,包含一个整数,表示成功报名的队伍数量。

样例

输入样例 1

3
5 2
1 2 3 1 1
5 2
3 1 4 1 5
6 1
2 3 1 3 1 2

输出样例 1

2
5
0

说明

对于第一个测试用例:

  • 在第 $1$ 秒,队伍 1, 4, 5 访问了报名网站。由于 $3 > 2$,网站在这一秒崩溃,这 3 支队伍报名失败。
  • 在第 $2$ 秒,队伍 2 访问了报名网站。由于 $1 \le 2$,网站没有崩溃,该队伍成功报名。
  • 在第 $3$ 秒,队伍 3 访问了报名网站。由于 $1 \le 2$,网站没有崩溃,该队伍也成功报名。
  • 共有 2 支队伍成功报名,因此答案为 2。

对于第二个测试用例:

  • 网站在任何一秒都没有崩溃,所有 5 支队伍均成功报名,因此答案为 5。

对于第三个测试用例:

  • 网站在前 3 秒的每一秒都崩溃了,所有 6 支队伍均报名失败,因此答案为 0。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.