ZOJ3790_Consecutive Blocks

给出一个数组，最多可以删除k个数，问能够获得的最长的一个数字连续段为多少？

把所有相同的数字都提取出来，保存取得每个数字需要删除的数字，然后二分枚举就可以了。

召唤代码君：

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

#define maxn 500200

using namespace std;

int a[maxn],b[maxn],first[maxn],next[maxn];

int Q[maxn],top,f[maxn];

bool vis[maxn];

int n,k,N,ans;

void go(int cur)

{

    vis[cur]=true;

    if (next[cur]!=-){

        go(next[cur]);

        Q[top++]=cur-next[cur]-;

    }

    else Q[top++]=;

}

int main()

{

    while (scanf("%d%d",&n,&k)!=EOF){

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

            scanf("%d",&a[i]);

            b[i]=a[i];

        }

        sort(b,b+n);

        N=unique(b,b+n)-b;

        for (int i=; i<n; i++) a[i]=lower_bound(b,b+N,a[i])-b+;

        memset(first,-,sizeof(int)*(n+));

        for (int i=; i<n; i++) next[i]=first[a[i]],first[a[i]]=i;

        memset(vis,false,sizeof(bool)*(n+));

        ans=;

        for (int i=n-; i>=; i--)

            if (!vis[i]){

                top=;

                go(i);

                for (int j=; j<top; j++) Q[j]+=Q[j-];

                for (int pos=; pos<top; pos++){

                    if (Q[top-]-Q[pos]<=k){

                        ans=max(ans,top-pos);

                        break;

                    }

                    int l=pos,r=top-,mid;

                    while (l<r){

                        mid=(l+r+)/;

                        if (Q[mid]-Q[pos]>k) r=mid-;

                            else l=mid;

                    }

                    ans=max(ans,l-pos+);

                }

            }

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

    }

    return ;

}