题解 | #组队#

📅 2025.11.04 每日一题

标签：排序 | 二分查找 / 双指针

今天时间不多，简单点说：
先排序 —— 这才是最关键的第一步！
之后用 二分查找 或 双指针 都可以高效求解。

双指针

using namespace std;
const int N=2e5+1;
int a[N];
int main(){
    int t;
    cin>>t;
    while(t--){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    int ans=0;
    for(int i=1,r=1;i<=n;i++){
        while(r<=n&&a[r]-a[i]<=k) r++;
        ans=max(ans,r-i);
    }
    cout<<ans<<endl;
    }
}

二分

using namespace std;
const int N=2e5+1;
int a[N];
int main(){
    int t;
    cin>>t;
    while(t--){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    int ans=0;
    for(int i=1;i<=n;i++){
        int mi=a[i],ma=a[i]+k;
        auto it1=lower_bound(a+1, a+1+n,mi);
        auto it2=upper_bound(a+1, a+1+n, ma);
        ans=max(ans,int(it2-it1));
    }
    cout<<ans<<endl;
    }
}