友情提示：380元/半年，儿童学编程，就上码丁实验室。
6
盒子
分析：对盒子的强度值进行排序有利于进行分组。我们先按盒子强度从小到大进行排序。可总结出以下的性质：
1、如果一个盒子的强度是x，那么它上面的盒子的个数就是<=x。
2、如果一个盒子的强度大于上面盒子的个数，那么这个盒子就是需要重新另开一组。
为了方面处理堆的数量变化以及堆的个数，我们可以利用stl中的集合，因为数值中有重复的值，我们选用multiset。这个集合当中的每个元素代表每个堆有多少个盒子。我们从小到大遍历盒子的强度值数组，只有堆的个数小于等于x，x才能加入该堆的最底部。如果最小堆的个数大于x，那么就要为x新建一堆。最后我们输出集合的个数即可。代码如下：
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
int x[500005];
int main(){
int n;
cin >> n;
for(int i =1;i <= n;i++){
cin >> x[i];
}
sort(x,x+n);//排序 0 1 1 2 2
//myse每个元素代表每个堆有几个盒子
multiset<int,greater<int>> myset;
for(int i =1;i <= n;i++){
//对于降序集合,lower_bound得到的是第一个小于x[i]的元素的位置
multiset<int>::iterator it = myset.lower_bound(x[i]);
//如果最小堆的个数大于x[i]，说明要为x[i]新建一个堆
if(it == myset.end()){
myset.insert(1);
}
else{
//当堆的个数小于等于x[i]，x[i]才能加入该堆的最底部。
//把元素加到这个堆里时，堆的元素个数加1
int cnt =*it +1;
myset.erase(it);
myset.insert(cnt);
}
}
cout << myset.size()<< endl;
return 0;
}
转自公众号：
noip案例讲解