Codeforces Contest 1156 C Match Points —— lower_bound

本文主要是介绍Codeforces Contest 1156 C Match Points —— lower_bound，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

给你n个数，让他们两两配对，要求每个数最多只有一个数与它匹配，并且两个数的差>=z，问你最大有多少对数可以匹配

题解：

非常敢单，但是有一些细节问题要注意一下。
首先我是先排序，再用lower_bound来做，但是lower_bound的时候要注意每个数只能找后半部分的数，因为找前面的数会出现一个问题：假设有1,10,15,20这四个数，z是9，那么如果lower_bound没有找后半部分的话，1就会找到10，但是15无法与20匹配，那么数量就少了1。
之后找到的位置可能是别人已经匹配过了，这时候for一遍会t，所以可以用并查集的方法去找之后的数。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N],vis[N];
int fa[N];
int finds(int x)
{return x==fa[x]?fa[x]:fa[x]=finds(fa[x]);
}
int main()
{int n,z;scanf("%d%d",&n,&z);for(int i=1;i<=n;i++)scanf("%d",&a[i]),fa[i]=i;fa[n+1]=n+1;sort(a+1,a+1+n);int ans=0;for(int i=1;i<=n;i++){if(fa[i]!=i)continue;int p=lower_bound(a+1+(n+1)/2,a+1+n,a[i]+z)-a;if(p>n)break;p=finds(p);if(p>n)break;fa[p]=fa[finds(p+1)];finds(p);ans++;}return 0*printf("%d\n",ans);
}

这篇关于Codeforces Contest 1156 C Match Points —— lower_bound的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---