C. New Game （二分）

时隔多年又做题了这不得来水一篇博客

题意：给出n个数，取一段连续的数字，最大数和最小数的差不超过k，使得取的数最多。

解：对于每一个数，找到第最后一个连续的且与其差值不大于k的数，数一数期间一共有几个，然后取最大值。实现上先处理出连续的段，对于每一个数，找到对应的段，二分找出差值不大于k的数即可。

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define maxx 200005
#define inf 1000000009
int n, k;
int a[maxx] = {0};
int sum[maxx] = {0};
int pre[maxx] = {0};

signed main(){
    int T;
    scanf("%d", &T);
    while (T--){
        scanf("%d%d", &n, &k);
        for (int i = 1; i <= n; i++){
            scanf("%d", &a[i]);
        }
        sort(a + 1, a + n + 1);
        a[n+1]=inf;
        sum[1] = 1;
        pre[1]=1;
        int now=1;
        pre[n]=n;
        for(int i=n-1;i>0;i--) {
            if (a[i+1] >= a[i] + 2){
                pre[i] = i;
            }
            else
                pre[i] = pre[i + 1];
        }
        int ans = 1;
        // for(int i=1;i<=n;i++) printf("%d ",a[i]); printf("\n");
        // for(int i=1;i<=n;i++) printf("%d ",sum[i]); printf("\n");
        // for(int i=1;i<=n;i++) printf("%d ",pre[i]); printf("\n");
        for(int i=1;i<=n;i++) {
            int l=i,r=pre[i],mid;
            // printf("%d\n",r);
            int ans1=l;
            while(l<=r){
                mid=l+(r-l)/2;
                if(a[mid] - a[i] + 1 <= k){
                    ans1=mid;
                    l=mid+1;
                }
                else
                    r=mid-1;
            }  
            // printf("%d ",ans1);
            ans = max(ans, ans1 - i + 1);
        }
        // printf("\n");
        printf("%d\n", ans);
    }
}