Siyuan

「Codeforces 1156C」Match Points
「Codeforces 1156C」Match Points
扫描右侧二维码阅读全文
19
2019/05

「Codeforces 1156C」Match Points

题目链接: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;
}

发表评论