3617:Best Cow Line

keyword

Greedy　C++

概要

プログラミングコンテストチャレンジブックで解説がつくらしいので予習の意味を込めて挑戦。
文字列が与えられる。文字列の最初か最後を取り除いて、新しい文字列として取り除いた文字をつなげていく。辞書順で最小の新しい文字列を求める問題。文字列の長さは2000以下。
今ある文字列と文字列を反転させたものを辞書順に比較すれば最初を取り除けば良いか最後を取り除けばよいか判定できる。実装で細かいミスを連発した(今回はFarmer Johnの問題にしては出力形式が面倒)けど無事AC。

int main(){
    int i, j, n, pos = 0, start, end;
    char cs[2002], ans[2002];
    string st, ed;

    scanf("%d\n",&n);
    REP(i,n) {scanf("%c",cs+i);scanf(" ");}
    start = 0;
    end = n-1;

    while(start < end){
        if(cs[start] != cs[end]){
            if(cs[start] < cs[end]){
                ans[pos++] = cs[start++];
            }
            else{
                ans[pos++] = cs[end--];
            }
        }
        else{
            st = string(cs+start, cs+(end+1));
            ed = st;
            reverse(ALL(ed));
            if(st < ed){
                ans[pos++] = cs[start++];
            }
            else{
                ans[pos++] = cs[end--];
            }
        }
    }

    ans[pos++] = cs[start];
    ans[pos] = '\0';
    for(i=80;;i+=80){
        cout << string(ans+(i-80), ans+(min(i,n))) << endl;
        if(i>=n) break;
    }

    return 0;
}