`
暴风雪
  • 浏览: 375021 次
  • 性别: Icon_minigender_2
  • 来自: 杭州
社区版块
存档分类
最新评论

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

阅读更多

大致题意:

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

 

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

 

#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;
}
 
0
0
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics