记录编号	597152	评测结果	AAAAAEAAAW
题目名称	又是决斗	最终得分	80
用户昵称	flyfree	是否通过	未通过
代码语言	C++	运行时间	1.367 s
提交时间	2024-11-25 15:12:02	内存使用	11.94 MiB

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 1000010 
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
ll t[MAXN],a[MAXN],n,sum[MAXN];
bool cmp(ll a,ll b){
	return a>b;
}
struct node{
	ll h[MAXN],siz;
	void insert(ll x){
		h[++siz]=x;
	}
	void mk(){
		ll _siz=siz;
		sort(h+1,h+1+siz);
		for(int i=1;i<=_siz;i++){
			if(h[i]==h[i+1]){
				h[i]=0;
				siz--;
			}
		}
		sort(h+1,h+1+_siz,cmp);
		sort(h+1,h+1+siz);
	}
	ll find(ll x){
		ll l=1,r=siz;
		while(l<r){
			ll mid=(l+r+1)/2;
			if(h[mid]<=x)l=mid;
			else r=mid-1;
		}
		return l;
	}
}pre;
int main(){
	freopen("duela.in","r",stdin);
	freopen("duela.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		pre.insert(a[i]);
//		t[a]++;
	}
	pre.mk();
	for(int i=1;i<=n;i++){
		t[pre.find(a[i])]++;
	}
	for(int i=1;i<=pre.siz;i++){
		ll s=min(t[i],t[i-1]),q=0;
		t[i]-=s,t[i-1]-=s;
		if(t[i]){
			q=min(sum[i-1],t[i]/2);
		}
		t[i]=t[i]+t[i-1]-2*q;
		sum[i]=sum[i-1]+s+q;
	}
	cout<<t[pre.siz];
	return 0;
}