75pts大样例过了求助
查看原帖
75pts大样例过了求助
1010629
qwqSW楼主2024/11/6 22:20

贪心做的,大鱼吃小鱼,小鱼吃虾米
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;
}
2024/11/6 22:20
加载中...