欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[贪心]poj 3623:Best Cow Line, Gold

程序员文章站 2022-07-12 16:20:00
...

大致题意:

    给你一个字符串,现在要生成一个新的字符串,规则是每次从原字符串的头部或者尾部取一个字符放在新字符串的尾巴上。求字典序最小的新字符串。

 

大致思路:
    正解是后缀数组,这里用贪心水过去了。

 

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=30005;
char str[nMax];
bool check(int a,int b){
    while(a<b){
        if(str[a]>str[b])return 1;
        if(str[a]<str[b])return 0;
        a++;
        b--;
    }
    return 0;
}
int main(){
    int n,i,j,head,tail;
    while(scanf("%d",&n)!=EOF){
        int cnt=0;
        head=0,tail=n-1;
        for(i=0;i<n;i++){
            cin>>str[i];
        }
        while(head<=tail){
            if(check(head,tail)==0){
                printf("%c",str[head]);
                cnt++;
                head++;
            }
            else{
                printf("%c",str[tail]);
                cnt++;
                tail--;
            }
            if(!(cnt%80))
            printf("\n");
        }
        if(cnt%80)
            printf("\n");
    }
    return 0;
}