## 问题描述 给定长度为N的字符串S，要构造一个长度为N字符串T。T是一个空串，反复执行下列任意操作： * 从S的头部删除一个字符，加到T的尾部； * 从S的尾部删除一个字符，加到T的尾部； 目标是要构造字典序尽可能小的字符串T。 **限制条件：** * 1<=N<=2000 * 字符串S只包含大写英文字母 **输入：** N = 6 S = "ACDBCB" **输出：** ABCBCD  ## 问题分析 从字典序的性质上看，无论T的末尾有多大，只要前面部分的较小就可以。所以我们可以试一下如下贪心算法： * 不断取S的开头和末尾中较小的一个字符放到T的末尾。 这个算法已经接近正确了，只是针对S的开头和末尾字符相同的情形还没有定义。在这种情形下，因为我们希望能够尽早使用更小的字符，所以就要比较下一个字符的大小。下一个字符也有可能相同，因此就有如下算法： * 按照字典序比较S和将S反转后的字符串S'。 * 如果S较小，就从S的开头取出一个文字，追加到T的末尾。 * 如果S'较小，就从S的末尾取出一个文字，追加到T的末尾。 ( 如果相同则取哪个都可以） ## Code ~~~ int n; char ch[maxn]; void solve() { // 剩余的字符串为ch[a],ch[a+1],...,ch[b] int a=0,b=n-1; int k=0; while(a<=b) { // 将从左起和从右起的字符串比较 int flag=0; for(int i=0;i+a<=b;i++) { if(ch[a+i]>ch[b-i]) { flag=0; break; } else if(ch[b-i]>ch[a+i]) { flag=1; break; } } if(!flag) printf("%c",ch[b--]); else printf("%c",ch[a++]); k++; } printf("\n"); } ~~~ 对应题目：[POJ3617](http://poj.org/problem?id=3617)