题目链接：Codeforces 1156C

在一条数轴上有 $n$ 个点 $x_1, x_2, \dots, x_n$，两个点 $i, j$ 可以匹配当且仅当两者都满足：

• 两个点 $i, j$ 都没有和别的点匹配。
• $\lvert x_i - x_j \rvert \ge z​$。

请求出最多可以匹配多少对点。

数据范围：$2 \le n \le 2 \times 10 ^ 5​$，$1 \le x_i, z \le 10 ^ 9​$

Solution

先对 $x_i$ 进行排序后二分答案 $k$，那么可以贪心地得到匹配 $(1, n - k + 1), (2, n - k + 2), \dots, (k, n)$。只要判断这些匹配是否都满足第二条约束即可。

时间复杂度：$\mathcal O(n \log n)$。

Code

#include <cstdio>
#include <algorithm>

const int N = 2e5 + 5;

int n, k, a[N];

bool check(int x) {
    for (int i = 1; i <= x; i++) {
        if (a[n - x + i] - a[i] < k) return false;
    }
    return true;
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    std::sort(a + 1, a + n + 1);
    int l = 0, r = n >> 1, ans = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        check(mid) ? l = (ans = mid) + 1 : r = mid - 1;
    }
    printf("%d\n", ans);
    return 0;
}