#643(Div.2)B. Young Explorers 题解
程序员文章站
2022-07-13 13:57:34
...
题目要求:分组,成员的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);
}
}
个人收获:
-
当循环内语句包含循环判定变量时,多使用for语句,这样对该变量的变化及范围了解得更加清晰。
-
#include <bits/stdc++.h> using namespace std;
万能头文件真的香,用起来省时方便。
-
scanf("%lld",&n); vector<int>e(n+1,0);
sacnf函数和vector容器一起用可以实现根据输入n来定义相应长度n的数组,感觉有点像动态数组,但比动态数组方便很多。
vector容器真的很好用较为全面的vector应用指南。
(我的代码逐渐C++化)
上一篇: oracle常用的几个例子