POJ3617-Best Cow Line

一道贪心，题目的意思就是说，给定一个字符串，每次只能从开头或者末尾取出一个字符加入到新串的末尾，使得到的字符串字典序最小。
因为每次只有两个选择（开头或末尾）所以先想到了dp，不过状态维护和比较大小不太容易，仔细一想其实是有贪心的，就是每次都把两个中更小的加入到新串末尾，因为越早加入新串，位置越靠前，字典序位置靠前优先级更高，自然得到的字典序更小。
如此一来就剩下一个问题就是如果两个字母相同，那么就再比较左右的下一位谁更小即可

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
char a[3000];
int n,ans[3000];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%c",&a[i]);
		while(!(a[i]<='Z'&&a[i]>='A')){
			scanf("%c",&a[i]);
		}
	}
	int l=1,r=n;
	for(int i=1;i<=n;i++){
		int ll=l,rr=r;
		while(ll<rr){
			if(a[ll]<a[rr]){
				ans[i]=l;l++;  //cout<<"&& "<<a[ans[i]]<<" "<<l<<endl;
				break;
			}
			else if(a[ll]>a[rr]){
				ans[i]=r;r--;  // cout<<"&& "<<a[ans[i]]<<endl;
				break;	
			}
			else if(a[ll]==a[rr]){
				ll++;rr--;
			}
		}
		if(ll>=rr){
			ans[i]=ll;	
		}
	}
	int cnt=0;
	for(int i=1;i<=n;i++){
		cnt++;
		printf("%c",a[ans[i]]);
		if(cnt==80){
			cnt=0;
			printf("\n");
		}
	}
	return 0;
	
}

这题还有一个很坑的地方就是每80个字母输出一行QAQ