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; }