题解 | 组队

void solve(){
    int n,k;cin>>n>>k;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a.begin()+1,a.end());
    int r=1;
    int ans=1;
    for(int i=1;i<=n;i++){
        while(r<=n&&a[r]-a[i]<=k)r++;
        ans=max(ans,r-i);
    }
    cout<<ans<<endl;
}

枚举每个数最为选择的最小数x，那么小于等于x+k的数都可以和他一起组队，那么我们可以二分的找到第一个大于x+k的数，即可计算出此时的最大值，比较每个数作为起点时产生的最大值即可知道最终答案，

另外我们发现，将数组排序后， 下标 i 产生的最大值一定小于 小标 i+1产生的最大值，那么我们知道 i 对应的最大值下标 r 后，i+1的最大下标一定在r的右侧，这样维护一个r即可做到在排序后O(n)的遍历 时间复杂度O(nlog(n)+n) O(nlog(n))