題意：將一個(gè)數(shù)列分成連續(xù)的三段，每段必須有數(shù)字，問這三段反轉(zhuǎn)后的數(shù)列的最小字典序的方案，并輸出，注意：第一個(gè)數(shù)比后面所有都大

思路：因?yàn)榈谝粋€(gè)數(shù)最大，那么將整個(gè)數(shù)列反轉(zhuǎn)后的字典序最小的后綴為第一段分開位置，但是要判斷情況，如最后還要至少剩下兩個(gè)數(shù)完成后兩段，接下來找第二段的分開位置，不可以像剛剛那么找了，想這個(gè)例子，將第一段去掉后是這樣的，1 3 2 1 100 如果和第一次一樣的方法結(jié)果是1 100 1 2 3 ，但是應(yīng)該是1 2 3 1 100，前四個(gè)為第二段，那么給如何處理，機(jī)智的人總是有辦法，不是我(/ □ /)，將這段反轉(zhuǎn)，再加上一段這樣的反轉(zhuǎn)，還是上面的例子，變成這樣100 1 2 3 1 100 1 2 3 1，然后求后綴數(shù)組，確定第二個(gè)分開位置，如果從第二個(gè)1分開，則它到倒數(shù)第二個(gè)位置的串就為原序列要求的結(jié)果，顯然它不是最優(yōu)，最優(yōu)的是第一個(gè)1開始，為1 2 3 1 100 ，這就是為什么加上兩次的原因

//poj 3581const int maxn = 200010;const int inf = 0x3f3f3f3f;int n,k;int rank1[maxn*2],tmp[maxn*2],sa[maxn*2],rev[maxn*2];int str[maxn],ans[maxn];bool compare_sa(int i,int j){    if(rank1[i] != rank1[j])        return rank1[i]<rank1[j];    else    {        int ri = i+k <= n? rank1[i+k] : -1;        int rj = j+k <= n? rank1[j+k] : -1;        return ri < rj;    }}void construct_sa(int *str1){    for(int i=0;i<=n;i++)    {        sa[i] = i;        rank1[i] = i<n?str1[i]:-1;    }    for(k=1;k<=n;k*=2)    {        sort(sa,sa+n+1,compare_sa);        tmp[sa[0]] = 0;        for(int i=1;i<=n;i++)        {            tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1],sa[i])?1 : 0);        }        for(int i=0;i<=n;i++)            rank1 [i] = tmp[i];    }}int main(int argc, const char * argv[]) {    // insert code here...    int nn;    scanf("%d",&nn);    for(int i=0;i<nn;i++)        scanf("%d",&str[i]);    for(int i=0;i<nn;i++)        rev[nn-1-i] = str[i];    n = nn;    construct_sa(rev);    int pos1,pos2;    for(int i=0;i<nn;i++)    {        pos1 = nn - sa[i];        if(pos1>=1&&nn-pos1>=2)            break;    }    for(int i=pos1-1;i>=0;i--)        PRintf("%d/n",str[i]);    int kk=0;    for(int i=nn-1;i>=pos1;i--)        rev[kk++]=str[i];    for(int i=nn-1;i>=pos1;i--)        rev[kk++]=str[i];    n=kk;    construct_sa(rev);    for(int i=0;i<=n;i++)    {        pos2 = pos1+n/2-sa[i];        if(pos2-pos1>=1&&nn-pos2>=1)            break;    }    for(int i=pos2-1;i>=pos1;i--)        printf("%d/n",str[i]);    for(int i=nn-1;i>=pos2;i--)        printf("%d/n",str[i]);    //std::cout << "Hello, World!/n";    return 0;}