1156C - Match Points（二分 贪心）

题意：

​ 给出一个整数n和一个整数z。代表下面有n个数，如果 a b s ( a [ i ] − a [ j ] ) > = z abs(a[i]-a[j])>=z abs(a[i]−a[j])>=z 则i j 两数可匹配。

​ 求数组中最大的匹配数

思路：

​ 我们考虑匹配数为 k k k的时候是否可以满足，那么按照贪心的思想，我们只需取出数组前 k k k个数和后 k k k个数 看看是否对应的能否匹配，如果可以满足则上述一定可以匹配，否则不能匹配。所以二分答案。

#include<bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof(a))
#define x first
#define y second
using namespace std;
typedef long long ll;
const double EPS=1e-10;
const int maxn=1e6+10;
int V[200045];
int n,z;
bool check(int m)
{
    for(int i=0;i<m;++i){
        if(V[n-m+i]-V[i]<z)
            return false;
    }
    return true;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>z;
    for(int i=0;i<n;++i) cin>>V[i];
    sort(V,V+n);
    int ans=0,l=1,r=n/2;
    while(l<=r)
    {
        int m=(l+r)>>1;
        if(check(m)){
            ans=m;
            l=m+1;
        }
        else
            r=m-1;
    }
    cout<<ans<<endl;
    return 0;
}