B题 离散化+双指针

最后找到的最大区间一定是以某一个点开始的，遍历每个数，看哪个数满足，复杂度2e9

优化：

排序之后把连在一起的一块当作一个点，两个连在一块的段中间没有数的块也当作一个点，记录这些块的长度，变为5e6复杂度，最大区间一定是以某一个块的第一个数为起点开始的。双指针维护每个块为起点能到达的最远距离。

#include<bits/stdc++.h>
using namespace std;
const int M = 1000010;
const int N = 500010;
int a[N];
int idx ;
long long n,m,k;
struct Node{
    int l,r,v;
}b[M];


int main(){
    ios::sync_with_stdio();
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>k;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n);
    int* nn = unique(a,a+n);
    n = nn - a;
    
    b[0] = {a[0],a[0],1};
    int right = a[0];
    
    for(int i=1;i<n;i++){
        if(a[i]-1 != right){
            idx++;
            b[idx] = {right+1,a[i]-1,0};
            idx++;
            b[idx] = {a[i],a[i],1};
            right = a[i];
        }else{
            b[idx].r = a[i]; 
            right = a[i];
        }
    }
    
    long long res = 0;
    long long zero_cnt = 0;
    long long this_res = 0;
    int i,j;
    for(i=0,j=0;i<=j && i<=idx && j<=idx;i++){
        while(j <= idx){
            int j_zero=0,j_one=0;
            if(b[j].v == 1){
                j_one = b[j].r - b[j].l +1;
            }else{
                j_one = b[j].r - b[j].l +1;
                j_zero = b[j].r - b[j].l +1;
            }
            
            if(zero_cnt + j_zero >k){
                break;
            }else{
                zero_cnt += j_zero;
                this_res += j_one;
                j++;
            }
        }
        
        
        long long val_res = min(m, this_res + k - zero_cnt);
        res = max(res,val_res);
        
        int i_zero=0,i_one = 0;
        if(b[i].v == 1){
            i_one = b[i].r - b[i].l +1;
        }else{
            i_one = b[i].r - b[i].l +1;
            i_zero = b[i].r - b[i].l +1;
        }
        if(i<j){
            zero_cnt -= i_zero;
            this_res -= i_one;           
        }else{
            j=i+1;
        }
        

    }
    
    cout<<res;
}