【贪心】POJ 3617：Best Cow Line

一、题目内容

POJ 3617 原题地址

二、题意解释

给定一个字符串，重排，每次从头或尾取较小值放到新序列的末尾。 题目要求是每80个为一行输出。

三、代码及注释

#include<cstdio> using namespace std; int n; char S[2001]; int main() { scanf("%d",&n); for(int j=0; j<n; j++) { scanf(" %c",&S[j]); } int l=0; int r=n-1; int ans=0; while(l<=r) { bool left=false; //不能简单的每次首尾比较取最小值，如果相等还需要继续看下一个要比较的对儿那个更小。 for(int i=0; l+i<=r; i++) { if(S[l+i]<S[r-i]) { left=true; break; } else if(S[l+i]>S[r-i]) { left=false; break; } } if(left) putchar(S[l++]); else putchar(S[r--]); ans++; if(ans%80==0) putchar('\n');//每80个换一行 } putchar('\n'); return 0; }