C. Match Points(二分)
给出一个整数n和一个整数z。代表下面有n个数,如果 abs(a[i]−a[j])>=z,则i j 两数可匹配。
求数组中最大的匹配数
求数组中最大的匹配数
一开始读错题啦拿并茶几写(居然还过了几组样例震惊)
这题二分的话,需要二分的当然就是匹配的数目,
每次匹配肯定是拿前mid个数字一次和后mid个数字进行匹配,然后就没了,,想到二分就很容易(读错题意的憨憨除外)
int main()
{
int n,z; cin>>n>>z;
vector<int>v(n); cin>>v;
sort(all(v));
int l=0,r=n/2,ans=0;
while(l<=r)
{
int mid=(l+r)>>1,flag=1;
rep(i,mid) if(v[i+n-mid]-v[i]<z) {flag=0;break;}
if(flag==1) ans=mid,l=mid+1;
else r=mid-1;
}
cout<<ans<<endl;
return 0;
} 
京公网安备 11010502036488号