Link

贪心,但不是无脑贪心.

一开始想的是,从小到大对于每个数 x x x找到第一个大于等于 x + z x+z x+z且没有被用过的数字让他们匹配

因为这样可以让后续的数字尽可能大

但是这样一来,剩下的数字都很大,然而差值却非常小,比 z z z还小,反而不能匹配,所以这个贪心是错的…

---

先对数组 a a a排序

考虑二分答案 k k k,那么选出最小的 k k k个数和最大的 k k k个数来匹配一定是最优的

我们让 a i a_i ai​和 a n − i + 1 a_{n-i+1} an−i+1​匹配,如果这都不行那就没办法了,时间复杂度 O ( n l o g ( n ) ) O(nlog(n)) O(nlog(n))

#include <bits/stdc++.h>
using namespace std; 
const int maxn =3e5+10;
int n,z,a[maxn];
bool isok(int k)
{
	for(int i=1,j=n-k+1;i<=k;i++,j++)
		if( a[j]-a[i]<z )	return false;
	return true;
}
signed main()
{
	cin >> n >> z;
	for(int i=1;i<=n;i++)	cin >> a[i];
	sort(a+1,a+n+1);
	int l = 1, r = n/2, ans = 0;
	while( r>=l )
	{
		int mid = l+r>>1;
		if( isok(mid) )	l = mid+1, ans = mid;
		else	r = mid-1;
	}
	cout << ans;
	return 0;
}