贪心做的,大鱼吃小鱼,小鱼吃虾米
WAon#1#3#17#19#20
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=1e5+5;
int n,a[N],b[N],f[N],ans,t,xd[N];
//xd:行动次数
//f:每个阶级的怪物个数 (考完才知道能求众数)
int main(){
//freopen("duel.in","r",stdin);
//freopen("duel.out","w",stdout);
scanf("%d",&n);
//cout<<"n="<<n<<endl;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
b[i]=a[i];
}
sort(b+1,b+n+1);
int len=unique(b+1,b+n+1)-b-1;//整了个离散化
if(len==1||n==1){//特判
printf("%d",n);
return 0;
}
//cout<<len<<endl;
for(int i=1;i<=n;i++){
a[i]=lower_bound(b+1,b+len+1,a[i])-b;
f[a[i]]++;
}
sort(a+1,a+n+1);
//for(int i=1;i<=n;i++){
// cout<<a[i]<<" ";
//}
//cout<<endl;
for(int i=1;i<=len;i++){
//cout<<f[i]<<" ";
xd[i]=f[i];
}
//cout<<endl;
t=1;
for(int i=2;i<=len;i++){
while(xd[i]&&t<i){
if(f[i]>=f[t]){//能吃干净
//ans+=f[t];
//cout<<"ans+="<<f[t]<<endl;
f[t]=0;
xd[i]-=f[t];
//cout<<i<<"has eaten"<<t<<endl;
t++;
}
else{//吃不干净
//ans+=f[i];
xd[i]=0;
//cout<<"ans+="<<f[i]<<endl;
f[t]-=f[i];
//cout<<t<<"still has"<<f[t]<<endl;
}
}
}
for(int i=1;i<=len;i++){
//cout<<f[i]<<" ";
ans+=f[i];//剩余个数
}
//cout<<endl;
//cout<<"ans="<<ans<<endl;
printf("%d",ans);
//fclose(stdin);
//fclose(stdout);
return 0;
}