题解 | #组队#

最近看到这种题满脑子都是二分，贴一个二分答案的写法，时间复杂度是O(nlogn)

#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>
typedef long long ll;
using namespace std;
const int N = 2e5 + 10;
ll a[N];    
int t, n, k;
bool check(int x)
{
    int b = 1, e = 1;//下标
    while (e <n)
    {
        if (a[e] - a[b] <= k)//中间差值是否小于k
        {
            if (e-b+1>= x)return true;//此时满足x个人的个数，返回
            e++;
        }
        else b++;//不是则往右移动区间
    }
    return false;
}
int main()
 {
    ios::sync_with_stdio(false);                    
    cin.tie(0);cout.tie(0);
    cin >> t;
    while (t--)
    {
        cin >> n >> k;
        for (int i = 1;i <=n;i++)
        {
            cin >> a[i];
        }
        sort(a + 1, a + n + 1);//进行排序,移动查找满足条件的最大区间
        int l = 0, r = n;
        while (l < r)
        {
            int mid = (l + r+1) >> 1;
            if (check(mid))l = mid;
            else r = mid - 1;
        }
        cout << l << endl;
    }
    return 0;
}

写完发现二楼大佬用upper_bound更快更简单。。没怎么用过这个工具，拙劣的效仿写了一个（一种不够简洁的复杂代码）

#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>
using namespace std;
int main() {
    ios::sync_with_stdio(false);                    
	cin.tie(0);cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n, k;
    cin >> n >> k;
        std::vector<int> abilities(n);
        for (int i = 0; i < n; ++i) {
           cin >> abilities[i];
        }

        sort(abilities.begin(), abilities.end()); // 将能力值数组排序

        int max_count = 0;

        for (int i = 0; i < n; ++i) {
            int end_index =upper_bound(abilities.begin(), abilities.end(), abilities[i] + k) - abilities.begin();
            int temp_count = end_index - i; // 计算当前选取的人员数量

            if (temp_count > max_count) {
                max_count = temp_count;
            }
        }

       cout << max_count <<endl;
    }
    return 0;
}