题面
Description
话说练习后缀数组时，小C 刷遍 poj 后缀数组题，
各类字符串题闻之丧胆。就在准备对敌方武将发出连环杀时，对方一记无中生有，又一招顺
手牵羊，小C 程序中的原字符数组就被牵走了。幸运的是，小C 早已经求出了 SA[]，为了
能东山再起，迅速 A 掉此题，他希望各位忠臣们能帮忙求出一组原字符数组的可行方案。已
知原字符数组由小写拉丁字母组成。且小C的SA[]也是有可能求错的， 原数组可能不存在。
Input
输入文件只有一行且为用空格隔开的一个正整数 N。
接下来一行有 N 个数，为 1~N 的排列。
其中对于 100%的数据 N≤500000
Output
一行有 N 个小写拉丁字母，若不存在合法方案输出-1；
Sample Input
4
2 3 4 1
Sample Output
dabc
解题思路
很有意思的一道题，自己动手模拟几个大概就能发现规律了。就是如果当前\(sa\)的后缀的位置如果大于下个\(sa\)后缀的位置，那么下一个的字典序一定比这个大，否则可以相等，所以\(O(n)\)扫一遍即可。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
const int MAXN = 500005;
inline int rd(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) f=ch=='-'?0:1,ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
return f?x:-x;
}
int sa[MAXN],nxt[MAXN],pos[MAXN];
int num,ans[MAXN],n;
int main(){
n=rd();
for(int i=1;i<=n;i++) sa[i]=rd(),pos[sa[i]]=i;pos[n+1]=0;
ans[sa[1]]=1;num=1;
for(int i=1;i<n;i++){
if(pos[sa[i]+1]<pos[sa[i+1]+1]) ans[sa[i+1]]=num;
else ans[sa[i+1]]=++num;
if(num>26) break;
}
if(num>26) puts("-1");
else for(int i=1;i<=n;i++) printf("%c",char(ans[i]+'a'-1));
return 0;
}