题目链接

https://ac.nowcoder.com/acm/contest/5158/B

分析题目

n人队伍，选取若干人，这若干人最大能力值和最小能力值的差值不能大于k，求最多能选取多少人。

解题思路

贪心嘛，自然情不自禁想排序，按能力值从小到大排序。
记得雨巨讲过“尺取法”（应该是）。先想象数轴，再确定一把尺子的长度，拿着确定长度的尺子在数轴上去取数。
这个题一样，排好序之后，遍历数轴以确定长度为k的尺子所对齐的左边界，在尺子右边界以外的点是不符合的，以内是符合的。
大概过程：
step1：升序排序
step2：遍历，尺取，记录尺子长度内的人数
step3：求max，输出

过程实现

我扔了俩代码，一个是我第一遍写的，是方法二对应的；方法一是我第二遍写的。
（为什么写俩？这说来话长……其实就是我开始写的超时了，找不到哪错了，就换了个方式实现，结果还是不行，才发现是数组开小了，忘记+10，回首发现，第一遍写的也对了……）

方法一：
这是比较简单的一串代码，用upper_bound函数找比 尺子左边界+尺子长度 大的第一个人所在的索引，找到了，但是这个人是尺子外的第一个点，所以-1，才是尺子内最右边的点。-a是为了求差，当前地址与首地址的差就是当前位置的索引。
保存最大值，输出。
时间复杂度：O(T*nlogn)
（你要还想减少时间，方法一的代码upper_bound的左边界可以改成a+i，其实对时间复杂度的影响不大，因为log级别的，开个根变化不大）

方法二：
简单的循环，遍历左边界，去找右边界，右边界一定是大于等于上一个左边界对应的右边界的，尺子的特点嘛。所以我们的时间复杂度并非2e5 * 2e5。每次循环完记得把记录当前尺子内人数的cnt自减一下，因为左边界右移了，左边的人出去了，自减之后，再在下一个尺子里继续上次的加就行了。
时间复杂度：O(T*nlogn)（好像是，我记不清了，错了不要打我qwq）

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;

inline int read(){
    int x=0,f=1;
    char ch;
    ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int a[N];
int T,n,k;
int main(){
    T=read();
    while(T--){
        n=read();k=read();
        for(int i=1;i<=n;i++)
            cin>>a[i];

        sort(a+1,a+n+1);

//——————————方法一 ——————————    

        int ans=0;
        for(int i=1;i<=n;i++){
            int tmp=upper_bound(a+1,a+n+1,a[i]+k)-a-1;
        //    cout<<"when i="<<i<<",tmp="<<tmp<<endl;//测试 
            ans=max(ans,tmp-i+1);
        }

//———————————————————————        

//——————————方法二 ——————————
/*
        int ans=0,cnt=1;
        for(int i=1,j=2;i<=n;i++){
            while(a[j]<=a[i]+k && j<=n) {cnt++;j++;}        
        //    cout<<"when i="<<i<<",cnt="<<cnt<<endl;//测试         
            ans=max(ans,cnt);
            cnt--;
        }
*/    
//———————————————————————    

        cout<<ans<<endl;
    }
}

哔哔赖赖

开始我还把题目当成了要求最大的能力值之和，发现数怎么这么大，和样例答案区别太大了吧，de了一小会才发现求的都不是一个东西。
快读函数，没必要，我就是为了让自己别忘了怎么写，写一遍熟悉一下。