[codeforces 1355B] Young Explorers 题意难懂 codeforces

Codeforces Round #643 (Div. 2)参与排名人数11475
[codeforces 1355B]Young Explorers题意难懂
总目录详见https://blog.csdn.net/mrcrack/article/details/103564004
【[codeforces 1355B] Young Explorers 题意难懂】在线测评地址https://codeforces.com/contest/1355/problem/B

Problem	Lang	Verdict	Time	Memory
B - Young Explorers	GNU C++17	Accepted	77 ms	4400 KB

一遍，两遍，三遍，都看不懂题意，无奈切换到C题，看懂了C题，也模拟成功了样例，感觉C题一时半会，编不出，继续切换到D题，比较粗略的弄懂了D题题意，无心在D题进行编写，看了看此时B题的通过情况，我的天，5000多了，看来要跟B题死磕，大不了，交代在B题。
题意最难懂的一句Russell decided that an explorer with inexperience e can only join the group of e
or more people.

什么意思呢，连蒙带猜，结合样例，才略微的有了些想法

3 1 1 1可进行如下分组情况1:{1},{1},{1} 情况2:{1,1},{1} 情况3:{1,1,1} 情况4:{1},{1},另一个待在营地情况5:{1,1},另一个待在营地情况6:{1},另2个待在营地情况7:另3个待在营地

5 2 3 1 2 2可进行如下分组情况1:{1},{2,2},2,3待在营地情况2:{1},{2,2,2},3待在营地情况3:{1,2,3},{2,2} 情况4:{1,2},{2,2},3待在营地情况5:{1,2},{2,2,3} ...... 少于2个分组的情况就不再枚举了。

明白题意后，为了尽可能多的分组，思路如下：
inexperience是1的每分1组，每组中最少的元素只有1个(可包含inexperience是1的元素);
inexperience是2的每分1组，每组中最少的元素只有2个(可包含inexperience是1,2的元素),多出的进入之后的分组;
inexperience是3的每分1组，每组中最少的元素只有3个(可包含inexperience是1,2,3的元素),多出的进入之后的分组;
inexperience是4的每分1组，每组最少的元素只有4个(可包含inexperience是1,2,3,4的元素),多出的进入之后的分组;
......
第一发WA后，才发现inexperience是2,多出的; inexperience是3,多出的; inexperience是4,多出的,是一个累加关系，可以累加后，进入下一轮分组，编码时没注意到。
AC代码如下

#include #define maxn 200010 int cnt[maxn]; int main(){ int t,n,i,a,tot,remain; scanf("%d",&t); while(t--){ tot=0,remain=0; //remain统计inexperience中多出的部分 scanf("%d",&n); for(i=1; i<=n; i++)cnt[i]=0; for(i=1; i<=n; i++)scanf("%d",&a),cnt[a]++; //cnt[i]记录inexperience是i的数量 for(i=1; i<=n; i++) tot+=(cnt[i]+remain)/i,remain=cnt[i]+remain-(cnt[i]+remain)/i*i; //注意i是指1个分组中最小的元素数量 printf("%d\n",tot); } return 0; }

类似题目
洛谷 P1089 津津的储蓄计划