bzoj 4319: cerc2008 Suffix reconstruction 贪心

如果字符集无限大的话直接按照 $sa$ 的顺序依次填即可. 

由于字符集非常小，所以要尽量填相同的字符.   

我们知道 $sa$ 数组，也就知道了 $rank$ 数组.   

那么考虑添加排名为 $i$ 的字符： 

如果 $rank[sa[i-1]+1]>rank[sa[i]+1]$，说明 $sa[i]$ 的字典序必须比 $sa[i-1]$ 的字典序大，新建字符.  

否则，就不用新建字符.  

这么做下去即可. 

code: 

#include <bits/stdc++.h>
#define N 503000
#define LL long long
using namespace std;
void setIO(string s)
{
    string in=s+".in";
    freopen(in.c_str(),"r",stdin);
}
char str[N];
int sa[N],rk[N];
int main()
{
    // setIO("input");
    int i,j,n;
    scanf("%d",&n);
    for(i=1;i<=n;++i)
    {
        scanf("%d",&sa[i]);
        rk[sa[i]]=i;
    }
    int ch=0;
    str[sa[1]]=ch+'a';
    for(i=2;i<=n;++i)
    {
        if(rk[sa[i]+1]<rk[sa[i-1]+1]) ++ch;
        if(ch>=27)
        {
            printf("-1\n");
            return 0;
        }
        str[sa[i]]=ch+'a';
    }
    printf("%s",str+1);
    return 0;
}