字典序最小问题——贪心

给定长度为n的字符串S，构造一个字典序最小的字符串T

操作：

1：从S的头部删除一个字符加到T尾部

2：从S的尾部删除一个字符加到T尾部

 

前后比较，如果前后相同，比较S与反转后的SS

如果S小，把S的开头加进去

如果SS小，把S的尾部加进去

例题：http://poj.org/problem?id=3617

#include <iostream>
using namespace std;
int main( ) {
    int n;
    cin>>n;
    char s[2005];
    for(int i=0;i<n;i++) cin>>s[i];
    
    int l=0,r=n-1;
    int cnt=0;
    while(l<=r) {
        bool k=false;
        for(int i=0;l+i<=r;i++) {
            if(s[l+i]<s[r-i]) {
                k=1;
                break;
            }
            else if(s[l+i]>s[r-i]) {
                k=0;
                break;
            }
        } 
        if(k) cout<<s[l++];
        else cout<<s[r--];
        cnt++;
        if(cnt%80==0) cout<<endl;
    }
    return 0;
}