民间数据100,官方数据75,WA了五个点
查看原帖
民间数据100,官方数据75,WA了五个点
1271676
Milkshakefairytale楼主2024/11/6 16:21
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int r[MAXN];
int a[MAXN];//多少个人 
int num[MAXN];//有多少能够发动攻击的 
int n;
int main()//大抵是AC 
{
// 	freopen("duel.in","r",stdin);
// 	freopen("duel.out","w",stdout);
 	cin>>n;
 	for(int i=0;i<=100001;i++)
 	{
 		a[i]=0;
 		num[i]=0; 
	}
 	for(int i=1;i<=n;i++)
 	{
 		cin>>r[i];
 		a[r[i]]++;
 		num[r[i]]++;
	}
	int flag=0,ans,anss;//ans表示剩下几个也就是输出的答案,anss表示还要杀死多少个 
	ans=n;
	for(int i=0;i<=100001;i++)
	{
		if(a[i])
		{
			if(flag==0)
			{
				flag=1;
				anss=a[i];
			}
			else
			{
				if(anss<=num[i])//这一批可以杀完 
				{
					ans=ans-anss;
					anss=a[i];
				}
				else//这一批杀不完,要更大的来杀 
				{
					ans=ans-num[i];//先杀完
					anss=anss-num[i];
					for(int j=i+1;j<=100001;j++)
					{
						if(num[j])
						{
							if(num[j]<anss)//这一轮没杀完,还要继续找
							{
								ans=ans-num[j];
								anss=anss-num[j];
								num[j]=0;
							}
							else//这一轮可以杀完
							{
								ans=ans-anss;
								anss=a[i];
								break;
							}
						}
					}
				}
			}
		}
	}
//	for(int i=1;i<=100001;i++)
//	{
//		if(a[i])
//		{
//			cout<<"有"<<a[i]<<"个"<<i<<endl;
//		}
//	}
	cout<<ans<<endl;
	return 0;
}
2024/11/6 16:21
加载中...