题目描述

给你一个在数轴上的点集$x_1, x_2, \dots, x_n$。
每两个点$i$,$j$可以在满足以下情况的时候相连:

  • 点$i$和点$j$均未与其他点相连;
  • $\left| x_i - x_j \right| \geq z$.

那么请你求出最多可以连接多少点对?

输入格式

第一行包含两个整数$n$和$z$$(2 leq n leq 2 cdot 10^5,,1 leq z leq 10^9)$—— 分别代表点的数量和连接点对时最长距离。
第二行包含$n$个整数$x_1, x_2, \dots, x_n\;(1 \leq x_i \leq 10^9)$.

输出格式

输出一个整数,代表最大能够互相连接的点对数量。

输入输出样例

输入 #1

4 2
1 3 3 7

输出 #1

2

输入 #2

5 5
10 9 5 8 7

输出 #2

1

分析

首先对点进行排序,然后通过二分来枚举答案,使两个端点不断相互逼近最优解即可得到答案。

时间复杂度$O(n·\log_2^n)$

代码

#include<bits/stdc++.h>
#define AC return 0;
using namespace std;
int n,m,l,r;
int a[200001];
inline int check(int k) {
    for (int i=1;i<=k;++i)
        if (a[n-k+i]-a[i]<m) return 0;
    return 1;
}
int main() {
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++){
        scanf("%d",&a[i]);    
    }
    sort(a+1,a+n+1);
    l=0,r=n/2;
    while (l<r) {
        int mid=(l+r+1)/2;
        if (check(mid)) l=mid;
        else r=mid-1;
    }
    printf("%d",l);
    AC
}
最后修改:2021 年 07 月 07 日 02 : 06 PM
如果觉得我的文章对你有用,请随意赞赏