【题解】Match Points
【题解】Match Points
MikeC
发布于 2022-09-21 11:45:44
发布于 2022-09-21 11:45:44
题目描述
给你一个在数轴上的点集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
© 允许规范转载
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021 年 07 月，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
