【题解】Match Points

题目描述

给你一个在数轴上的点集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

代码语言：javascript复制

4 2
1 3 3 7

输出 #1

代码语言：javascript复制

2

输入 #2

代码语言：javascript复制

5 5
10 9 5 8 7

输出 #2

代码语言：javascript复制

1

分析

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

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

代码

代码语言：javascript复制

#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

© 允许规范转载

match

0 人点赞