[贪心]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; }