如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY 4.0 （除特别声明或转载文章外）
看到此题，第一个想法：仿桶排序！
于是就这样做。
输入是：0 1 2 2 3 3 3 4
数组键值表：
0 1 2 3 4
1 1 2 3 1
碰到值大于0，就开始分组，一口气分到不能再分为止。这个案例，分组就是：
0 1 2 3 4
2 3
3
emmm…不对啊，正确答案是2
0 1 2 3
2 3
3 4
那怎么办？！！第一次分组时应该只分到3，刚好这个值在3的时候第一次下降。
考虑在数量第一次下降时停止分组。
#include<iostream>
using namespace std;
short int es[2000000078];
int main(){
int n,a=2e9;cin>>n;
for(int i=0;i<n;i++){
int f;cin>>f;
es[f+(int)1e9]++;
}
while(1){
int m,q=0;
for(m=0;!es[m]&&m<=2e9+10;m++);
if(m>2e9)break;
for(;es[m]<=es[m+1];m++,q++)es[m]--;
es[m]--;
a=min(a,q+1);
}
cout<<a<<endl;
}
结果惨不忍睹
$\color{white} WTF？！$
果然是内存不足了，早知道我就不开那么大的数组 结果60分
emmm…后来就想到了用map
用iterator来遍历，还是上面的思路，但是要记住最后如果降为0要把它erase掉
贴代码：
#include<iostream>
#include<map>
using namespace std;
map<int,int>es;
int main(){
int n,a=2e9;cin>>n;
for(int i=0;i<n;i++){
int f;cin>>f;
es[f]++;
}
while(!es.empty()){
int q=1;
map<int,int>::iterator m=es.begin();
int sm=(*m).first;
for(;es[sm]<=es[sm+1];sm++,q++)es[sm]--;
es[sm]--;
a=min(a,q);
while(m!=es.end()&&(*m).second==0)es.erase((*m++).first);
}
cout<<a<<endl;
}