欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

#643(Div.2)B. Young Explorers 题解

程序员文章站 2022-07-13 13:57:34
...

#643(Div.2)B. Young Explorers 题解
题目要求:分组,成员的e值必须小于本组人数,求最大小组数。

解题思路:贪心,在限制条件下利益最大化。为保证小组数量最大,按e = 1可自成一族的成员分到多人组就是浪费的思路,依据e从小到大分组。

AC代码:

#include <bits/stdc++.h>
using namespace std;

int main(){
	long long t,n;
	scanf("%lld",&t);
	
	while(t--)
	{
		scanf("%lld",&n);
		vector<int>e(n+1,0);//实现简单的“动态数组”
		for(int j=1;j<n+1;j++)
		{
			scanf("%d",&e[j]);
		}
		sort(e.begin()+1,e.end());//对e排序
		int ans = 0,cnt = 0;//ans组数,cnt组员数
		for(int k=1;k<n+1;k++)//分组
		{
			cnt++;
			if(cnt >= e[k])//如果该成员e值小于组员数,则分组成功,ans+1,cnt置零。否则继续录入下一个组员进入本小组
			{
				ans++;
				cnt=0;
			}
		}
		printf("%d\n",ans);
	}
}

个人收获:

  1. 当循环内语句包含循环判定变量时,多使用for语句,这样对该变量的变化及范围了解得更加清晰。

  2. #include <bits/stdc++.h>
     using namespace std;
    

    万能头文件真的香,用起来省时方便。

  3. scanf("%lld",&n);
    vector<int>e(n+1,0);
    

    sacnf函数和vector容器一起用可以实现根据输入n来定义相应长度n的数组,感觉有点像动态数组,但比动态数组方便很多。
    vector容器真的很好用较为全面的vector应用指南

(我的代码逐渐C++化)

相关标签: OI icpc