Algoogle

Algorithm for Programming Contest

PKU 3617 Best Cow Line

Category: PKU Tag: greedy

Best Cow Line

問題概要


解法


基本greedyに取っていって, 前後同じの時は残りの牛を1列に並べて
前からみるのと後ろから見るのを辞書順で比較して, 小さい方から取っていく.
書いていて気づいたが, 常にstringで反転したやつと比較するだけでよいのでは……

コード


(3617.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <algorithm>
#include <cstdio>
#include <string>

using namespace std;

int N;
string seq = "";
string ans = "";

int main(){
    scanf("%d\n", &N);
    for(int i = 0; i < N; i++){
        char c; scanf("%c\n", &c);
        seq.push_back(c);
    }
    int l = 0, r = N-1, len = 0;
    while(l <= r){
        if(seq[l] < seq[r]) ans.push_back(seq[l++]);
        else if(seq[l] > seq[r]) ans.push_back(seq[r--]);
        else{
            string ls = seq.substr(l,N-len);
            string rs = seq.substr(l,N-len);
            reverse(rs.begin(), rs.end());
            if(ls < rs) {
                ans.push_back(ls[0]);
                l++;
            }
            else {
                ans.push_back(rs[0]);
                r--;
            }
        }
        len++;
    }
    for(int i = 0; i <= N / 80 - int(N % 80 == 0); i++){
        for(int j = 0; j < min(N-i*80,80); j++)
            printf("%c", ans[i*80+j]);
        printf("\n");
    }
    return 0;
}

Comments