Match Points

Created by LXC on Sat May 13 13:22:48 2023

https://codeforces.com/problemset/problem/1156/C

ranting: 2000

tag: binary search, greedy, sortings, ternary search, two pointers

题意

给出一个长度为n的数组a和整数z，求最大匹配的数对。

匹配的数对是指：
数组中的两个元素的差的绝对值大于等于z。
并且这两个数没有和其他数匹配。

题解

先将数组排序。

二分答案。

如果答案是k，那么最小的k个数和最大的k个数匹配，如果匹配的任意两个数都是大于等于z的，那么不断增大k直到找到最后一个满足匹配的k。

代码

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    ll n, z;
    cin >> n >> z;
    vector<ll> a(n);
    for (ll& i : a)
        cin >> i;
    sort(a.begin(), a.end());
    auto check = [&](int x) {
        for (int i = 0; i < x; i++) {
            if (a[n - x + i] - a[i] < z)
                return false;
        }
        return true;
    };
    int l = 1, r = n / 2 + 1;
    while (l < r) {
        // cout << l << " " << r << endl;
        int m = l + r >> 1;
        if (check(m)) {
            l = m + 1;
        } else {
            r = m;
        }
    }
    cout << r - 1 << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}