民间数据100,官方数据75,WA了五个点
查看原帖
民间数据100,官方数据75,WA了五个点
1271676
Milkshakefairytale楼主2024/11/6 16:20
#include<bits/stdc++.h>
using namespace std;
int n;
const int MAXN=1e5+5;
int a[MAXN];
int b[MAXN];
int flag[MAXN];
int main()
{
// 	freopen("duel4.in","r",stdin);
// 	freopen("duel4.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		b[a[i]]++;
		flag[a[i]]++;
	}
	int sum=0;
	int anss,ans;
	ans=n;
	for(int i=1;i<=100001;i++)
	{
		if(b[i]!=0)
		{
			if(sum==0)
			{
				sum=1;
				anss=b[i];
			}
			else
			{
				if(flag[i]>=anss)//杀的完 
				{
					flag[i]-=anss;
					ans=ans-anss;
					anss=b[i];
				}
				else//杀不完 
				{
					anss-=flag[i];
					ans-=flag[i];
					for(int j=i+1;j<=100001;j++)
					{
						if(flag[j]!=0)
						{
							if(flag[j]>=anss)//这一轮杀完了
							{
								flag[j]=flag[j]-anss;
								ans=ans-anss;
								anss=b[i];
								break;
							}
							else
							{
								ans-=flag[j];
								anss-=flag[j];
								flag[j]=0;
							}
						}
					}
				}
			}
		}
	}
	cout<<ans<<endl;
	return 0;
 } 
2024/11/6 16:20
加载中...