Codeforces Round #643 (Div. 2) B.Young Explorers 题目链接
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.
Input The first line contains the number of independent test cases T(1≤T≤2e5). 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≤2e5).
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 3e5.
Output 【Codeforces|Codeforces Round #643 (Div. 2) B.Young Explorers】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.
Example
input
2
3
1 1 1
5
2 3 1 2 2
output
3
2
这题乍一看不知道如何下手，其实只需要模拟即可，用贪心的策略即可保持最优，从小到大依次安排即可，AC代码如下：
#include
using namespace std;
typedef long long ll;
main(){
int t,n;
cin>>t;
while(t--){
cin>>n;
int e[n],mx=0,num=0,cnt=0;
for(int i=0;
i>e[i];
sort(e,e+n);
for(int i=0;
i 推荐阅读
- codeforces B. Young Explorers
- codeforces C. Mere Array
- codeforces D. Omkar and Bed Wars
- codeforces C. Omkar and Waterslide
- codeforces B. Omkar and Infinity Clock
- codeforces B. Ternary Sequence
- 题库-CF|【Codeforces Round 370 (Div 2) E】【线段树 等比数列 区间合并】Memory and Casinos 赌场区间[l,r] l进r先出的概率
- 题库-CF|【Codeforces Round 263 (Div 2)C】【贪心 哈弗曼思维】Appleman and Toastman 每个非1size子树延展为2子树的最大权
- Codeforces|Codeforces Round #605 (Div. 3) D. Remove One Element