[SPOJ 744]连续最长1..M排列

【题目大意】给定一个1..N的序列，然后让你求一段连续的子串包含1..M中所有的数字，且不重复。最后输出max(M)

【算法分析】

定义S[I]=前I个数的和。

NEXT[I]为下一个和当前这个数相同的数的位置

LAST[I]为前一个和当前这个数相同的数的位置

如果输满足条件的一个连续串的话，必然是没有重复的数字的，并且和为(M+1)*M/2。（等差数列求和）

已知结果串必然包含1，所以我们以1为标志，进行左右扫描。

情况1

假设这个1所能达到的最大M在左边，i为这个1的位置，则j向左扫描

q=max(a[j],q)

p=min(next[j],q)

显然p不能<=i，另外j+q-1

情况2和情况1对称，不再赘述。

【其它】1A

3251945 2010-02-09 16:03:34 cwj Longest Permutation accepted 0.96 4.7M

C++

4.3.2

【CODE】

#include #include #define min(x,y) (x)<(y)?(x):(y)
#define max(x,y) (x)>(y)?(x):(y)
const int N=111111;
int n,a[N],last[N],next[N],lpos[N],s[N];

void init(){
    s[0]=0;
    for (int i=1;i<=n;i++){
        s[i]=s[i-1]+a[i];
        next[lpos[a[i]]]=i;
        last[i]=lpos[a[i]];
        lpos[a[i]]=i;
    }   
    for (int i=1;i<=n;i++)
      if (lpos[i]!=0) next[lpos[i]]=n+1;
}   

void work(){
    int ans=0;
    for (int i=1;i<=n;i++)
      if (a[i]==1){
          ans=max(1,ans);
          int q=1,p=next[i];
          for (int j=i;j>last[i];j–){
              q=max(a[j],q);
              p=min(next[j],p);
              if (p<=i) break;
              if (j+q-1<=n && j+q-1

                ans=max(ans,q);
          }   
          q=1,p=last[i];
          for (int j=i;j              q=max(a[j],q);
              p=max(last[j],p);
              if (p>=i) break;
              if (j-q+1>=1 && j-q+1>p && s[j]-s[j-q]==q*(q+1)/2)
                ans=max(ans,q);
          }   
      }
    printf("%dn",ans);   
}   

int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    init();
    work();
}