CF1355B.Young Explorers
普及-
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Young wilderness explorers set off to their first expedition led by senior explorer Russell. Explorers went into a forest, set up a camp and decided to split into groups to explore as much interesting locations as possible. Russell was trying to form groups, but ran into some difficulties...
Most of the young explorers are inexperienced, and sending them alone would be a mistake. Even Russell himself became senior explorer not long ago. Each of young explorers has a positive integer parameter ei — his inexperience. Russell decided that an explorer with inexperience e can only join the group of e or more people.
Now Russell needs to figure out how many groups he can organize. It's not necessary to include every explorer in one of the groups: some can stay in the camp. Russell is worried about this expedition, so he asked you to help him.
年轻的野外探险者们在资深探险家罗素的带领下,开启了他们的首次远征。探险者们进入森林,建立了营地,并决定分成若干小组,以尽可能多地探索有趣的地点。罗素正尝试组建这些小组,却遇到了一些困难……
大多数年轻探险者缺乏经验,单独派遣他们显然是个错误。事实上,罗素本人成为资深探险家也没多久。每位年轻探险者都有一个正整数参数 ei —— 表示他的“缺乏经验值”。罗素决定:一位缺乏经验值为 e 的探险者,只能加入人数不少于 e 人的小组。
现在,罗素需要计算他最多能组成多少个小组。并非所有探险者都必须被分配到某个小组中——部分人可以留在营地。罗素对这次远征十分担忧,因此请你帮助他。
输入格式
The first line contains the number of independent test cases T(1≤T≤2⋅105). Next 2T lines contain description of test cases.
The first line of description of each test case contains the number of young explorers N (1≤N≤2⋅105).
The second line contains N integers e1,e2,…,eN (1≤ei≤N), where ei is the inexperience of the i-th explorer.
It's guaranteed that sum of all N doesn't exceed 3⋅105.
第一行包含独立测试用例的数量 T(1≤T≤2⋅105)。接下来的 2T 行包含各测试用例的描述。
每个测试用例的描述的第一行包含年轻探险家的数量 N(1≤N≤2⋅105)。
第二行包含 N 个整数 e1,e2,…,eN(1≤ei≤N),其中 ei 表示第 i 位探险家的缺乏经验值(inexperience)。
保证所有测试用例中 N 的总和不超过 3⋅105。
输出格式
Print T numbers, each number on a separate line.
In i-th line print the maximum number of groups Russell can form in i-th test case.
输出 T 个数字,每个数字占一行。
在第 i 行输出 Russell 在第 i 个测试用例中最多能组成的组数。
输入输出样例
输入#1
2 3 1 1 1 5 2 3 1 2 2
输出#1
3 2
说明/提示
In the first example we can organize three groups. There will be only one explorer in each group. It's correct because inexperience of each explorer equals to 1, so it's not less than the size of his group.
In the second example we can organize two groups. Explorers with inexperience 1, 2 and 3 will form the first group, and the other two explorers with inexperience equal to 2 will form the second group.
This solution is not unique. For example, we can form the first group using the three explorers with inexperience equal to 2, and the second group using only one explorer with inexperience equal to 1. In this case the young explorer with inexperience equal to 3 will not be included in any group.
在第一个例子中,我们可以组织三个小组,每个小组仅包含一名探险者。这种分组方式是正确的,因为每名探险者的经验值均为 1,不小于其所在小组的规模。
在第二个例子中,我们可以组织两个小组:经验值为 1、2 和 3 的三名探险者组成第一组,其余两名经验值均为 2 的探险者组成第二组。
该解法并不唯一。例如,我们也可以让三名经验值均为 2 的探险者组成第一组,仅让一名经验值为 1 的探险者组成第二组;此时,那名经验值为 3 的年轻探险者将不被包含在任何小组中。
输入解题思路,AI测评打分。不知道怎么写?