【题解】美好配对

题意

给你一个长度为数组，每个元素只能用一次，问从中配对的对数最多有多少对。

题解

可以考虑排序后从数组中找一个最长的段，该段满足，那么答案就是，因为但大于后，答案只能是另一半。
找最长段时可以用双指针法来找。

复杂度

时间复杂度

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int a[N];
int main()
{
    int n, k, ans = 0;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    sort(a+1,a+1+n);
    int l=1,r=1;
    int num=0;
    for(; r <= n; r++)
    {
        while(a[l] + k <= a[r])
            l++;
        num = max(num, r - l + 1);
    }
    printf("%d\n", min(n / 2, n - num));
    return 0;
}