盒子

Description

小D在玩堆盒子的游戏，每个盒子有一个强度，代表它上方最多能堆多少个
盒子。由于盒子都是一样大的，所以不能在一个盒了上并列放超过一个盒子。
现在小D有n个盒子，第i个盒子的强度为xi。

小D想知道，如果他要把这些盒子全部堆起来，至少要堆多少堆。

Input

第一行读入一个整数n，代表小D有的盒子个数。
第二行读入n个整数，第i个整数xi表示第i个盒了的强度。

Output

共一行，一个整数表示小D至少要堆多少堆。

Sample Input

5
0 2 1 1 2

Sample Output

2

Hink

对于20%的数据，n≤10;
对于50%的数据，n≤1000;
对于100%的数据，n≤500000，xi≤1000000000。

解题思路

先把盒子的强度从小到大排序，盒子的状态全部改为1（表示没有加进去 ），然后用一个计数器，计数器先清零。然后从第一个开始，如果盒子的强度大于计数器，计数器加1，盒子的状态清零（表示已经加进去了）。所有数全部过一遍，过完一次总数加1，计数器清零，知道盒子的状态全部为零结束。

#include<iostream>
#include<iomanip>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=10001;
int n,i,ans=0,t=0;//计数器清零，总数清零
struct cd
{
   
	int qd;
	bool zt;
};
cd a[500010];
bool cmp(cd a1,cd b1)
{
   
	return a1.qd<b1.qd;
}
void input()
{
   
	cin>>n;
	for(i=1;i<=n;i++)
	{
   
		cin>>a[i].qd;
		a[i].zt=1;
	}
}
bool comp(cd c[],int p)
{
   
	int ok1=0;
	int o;
	for(o=1;o<=p;o++)
	 if(c[o].zt!=0)
	 {
   
	 	ok1=1;
	 	break;
	 }
	if(ok1==0) return 1;
	else return 0;
}//判断是否还有遗漏
void work()
{
   
	sort(a+1,a+n+1,cmp);
	while(comp(a,n)==0)
	{
   
		ans=0;
		for(int i=1;i<=n;i++)
		{
   
			if(a[i].zt==0) continue;
			if(a[i].qd>=ans)//判断盒子的强度是否大于计数器
			{
   
				ans++;//计数器加1
				a[i].zt=0;//盒子状态清零 
			}
		}
		if(ans!=0) t++;
	}
}
void output()
{
   
	cout<<t;
}
int main()
{
   
	input();
	work();
	output(); 
	return 0;
}

注：

本人第一次发博客，如有不足请提出