The Longest Straight FZU - 2216 二分

题意

有n张卡片,每个卡片代表了从1到M的一个数字(可能重复), 这n个卡片中还可能有零,可以用来代表任何从1到M的数字,求最长的连续序列是多少

分析

1 先建立数组, 若在i的位置有一个卡片, 则标记为真,
2 然后用sum数组记录从1到i总共有多少个空缺,
3 再用一个left数组记录每一段已经有卡片的最左边的数字,
4 然后对于每一个left,从left[i] 到 M 二分求最大值, 即求从left[i]开始的最长序列是多少(需要增加一个1,因为可能从1开始)

参考代码

const int LEN = 123456;
int sum[LEN];
int ar[LEN];
int Left[LEN];
int maxlen;
int N,M;
void  check(int x,int zero)//从x到M的最长序列是多少
{
    if(!ar[x])
        zero--;
   // if(x+zero>=M)
   // {
       //maxlen = max(maxlen,M-x+1);
   // return ;
  // }
    int spaces = sum[M]-sum[x];
    if(zero>=spaces)////如果从x到M的空缺数量小于0卡片的数量, 
       //最长序列就是M-x+1
    {
        maxlen = max(maxlen,M-x+1);
        return ;
    }
    int l = x,r = M;//否则进行二分操作
    while(r-l>1)
    {
        int mid = l+(r-l)/2;
        if(sum[mid]-sum[x]==zero)
            l = mid;
        else if(sum[mid]-sum[x]>zero)
              r = mid-1;
        else if(sum[mid]-sum[x]<zero)
              l = mid+1;
    }
    if(sum[r]-sum[x]==zero)
        maxlen = max(maxlen,r-x+1);
    else
        maxlen = max(maxlen,l-x+1);
}
int main(void)
{

    int T;
    cin>>T;
    while(T--)
    {
        maxlen = 0;
        me(ar);
        me(sum);
        me(Left);

        cin>>N>>M;
        int Zero = 0;
        while(N--)
        {
            int a;
            scanf("%d",&a);
            if(a==0)
                ++Zero;
            else
                ar[a] = 1;
        }
        ar[0] = 1;
        bool sign = false;
        int num = 1;
        for(int i = 1; i <= M; ++i)
        {
            sum[i] = sum[i-1] + !ar[i];
            if(!sign&&ar[i])
            {
                Left[num++] = i;
                sign = true;
            }
            if(sign&&!ar[i])
                sign=false;
        }

        check(1,Zero);//可能从1开始
        for(int i = 1; i < num; ++i)
        {
            check(Left[i],Zero);
        }
        cout<<maxlen<<endl;
    }
    return 0;
}