题解 | #相差不超过k的最多数#

#include <stdio.h>
#include<stdlib.h>

void merge(int *arr,int l,int m,int r)
{
    int templ=l,tempr=m+1,sum=0;
    int *temp=(int *)malloc((r-l+1)*sizeof(int));
    while(templ<=m&&tempr<=r)
    {
        if(arr[templ]>arr[tempr])
        temp[sum++]=arr[templ++];
        else temp[sum++]=arr[tempr++];
    }
    while (templ <= m) { 
        temp[sum++] = arr[templ++];
    }
    while (tempr <= r) { 
        temp[sum++] = arr[tempr++];
    }
    for(int i=0;i<sum;i++)
    {
        arr[l+i]=temp[i];
    }
    free(temp);
}

void msort(int *arr,int l,int r)
{
    int m=l+(r-l)/2;
    if(l<r)
    {
        msort(arr,l,m);
        msort(arr,m+1,r);
        merge(arr,l,m,r);
    }
}

int arr[200000];
int main() 
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&arr[i]);
    }
    msort(arr,0,n-1);
    int l=0,r=1,mx=0;
    for(int i=l;i<n-1;i++)
    {
        while(r<n&&arr[i]-arr[r]<=k)
        {
            if(r-i+1>mx) mx=r-i+1;
            r++;
        }
    }
    printf("%d\n",mx);
    return 0;
}