盒子

小D在玩堆盒子的游戏,每个盒子有一个强度,代表它上方最多能堆多少个
盒子。由于盒子都是一样大的,所以不能在一个盒子上并列放超过一个盒子。
现在小D有n个盒子,第i个盒子的强度为xi。小D想知道,如果他要把这些盒
子全部堆起来,至少要堆多少堆。
Input
第一行读入一个整数n,代表小D有的盒子个数。
第二行读入n个整数,第i个整数xi表示第i个盒子的强度。
Output
一个整数表示小D至少要堆多少堆。
n≤500000,xi≤1000000000。
Sample Input
5
0 2 1 1 2
Sample Output
2

/*
将所有盒子从小到大排序。然后一个个加,这时不再关心盒子本身的那个所谓堆数的限制
拿样例来说,0 1 1 2 2
由于可能要摆成多个盒子堆,对于每个盒子堆,我们只是记其容量值,并将这些值丢入一个小根堆中,
当要加入一个新数字a时,此时我们要确定它放到哪个盒子堆中,或者说是要新开一堆出来。
于是拿出容量最小的那个堆的容量值b出来,如果a>=b,则说明这个数字可放到这一堆中
(其实也不是说一定要放到这一堆中,只要条件允许,随便放一堆都是可以的,但使用堆这种数据结构
可以很快知道是否要新开一个盒子堆出来)
于是放入,并将其容量值加1,再放回堆中。如果a<b,则说明当前数字不能放入任何一个盒子堆中,于是新加一个盒子堆出来。
对于第一个数字0,将这个盒子放到第一个盒子堆中,其容量记值为1,将数字1丢入一个堆中
对于第二个数字1,其值大于等于目前堆顶元素,所以可以加到这个盒子堆中,盒子堆的体积变2.
对于第三个数字1,由于此时堆顶元素值为2,说明1不能放入其中,于是另开一个盒子堆出来,记其体积为1,于是堆中有两个数字1,2。
对于第四个数字2,堆顶元素为1,说明2可以放于其中,于是堆中有了两个数字2,2
对于第五个数字2,堆顶元素为2,说明2可以放于其中,于是堆中有了两个数字2,3.
*/

#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=5e5;
int n,m;
int x[maxn+8];
priority_queue<int,vector<int>,greater<int> >que;

int read()
{
	int x=0,f=1;char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
	for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*f;
}

int main()
{
	m=read();
	for (int i=1;i<=m;i++)
		{
			int tmp=read();
			x[++n]=tmp;
		}
	sort(x+1,x+n+1);
	int ans=1;
        que.push(1);
	for (int i=2;i<=n;i++)
		{
			int p=que.top();
//弹出堆顶元素,它代表了各堆盒子中,容量最小的那个盒子堆。
			if (p<=x[i]) 
//如果x[i]大于p,说明其可以加到这个盒子堆中
                            que.pop(),que.push(p+1);
//弹出堆顶元素,容量加1,再放回去
			else 
                             ans++,que.push(1);
//说明第i个数字不能放于目前所有盒子堆任意一个,于是再加一个盒子堆出来
		}
	printf("%d\n",ans);
	return 0;
}
			

  

原文地址:https://www.cnblogs.com/cutemush/p/11745344.html