Accept: 17    Submit: 39
Time Limit: 1000 mSec    Memory Limit : 32768 KB

 Problem Description

 Input

 Output

 Sample Input

 Sample Output

 Source

第六届福建省大学生程序设计竞赛-重现赛（感谢承办方华侨大学）

 

 

题目大意：Zb在玩卡牌游戏，给你n张牌，一个m，每个牌面是在1~m之间的一个数，包括1和m。但是可能会有王牌，王牌可以变成1~m中的任意一个，这里王牌用0表示。问你最长的连续上升的牌的长度。

#include<stdio.h>

#include<algorithm>

#include<string.h>

#include<iostream>

using namespace std;

const int maxn = 1e6+200;

int card[maxn],presum[maxn];

int BinSearch(int l,int r, int k,int key){

    int mi = (l+r)/2;

    while(l < r){

        mi = (l+r)/2;

        if(presum[mi]-k > key){

            r = mi;

        }else{

            l = mi+1;

        }

    }

    if(presum[l]-k > key)

        l--;

    return l;

}

int main(){

    int T,n,m;

    scanf("%d",&T);

    while(T--){

        int a, Zero = 0;

        scanf("%d%d",&n,&m);

        memset(card,0,sizeof(card));

        for(int i = 1; i <= n; i++){

            scanf("%d",&a);

            card[a] = 1;

            if(!a) Zero++;

        }

        for(int i = 1; i <= m; i++){

            presum[i] = presum[i-1] + (!card[i]);

        }

        int ans = 1;

        for(int i = 1; i <= m; i++){

            int idx = BinSearch(i,m,presum[i-1],Zero);

          //  printf("%d ",idx);

            ans = max(ans, idx-i+1);

        }

        printf("%d\n",ans);

    }

    return 0;

}

/*

55

11 15

0 0 1 2 4 5 8 9 11 13 14

*/