POJ-3617 Best Cow Line
题面
多组测试数据
给你一个长度为N的字符串S,输入格式是依次输入N个字符
N <= 2000
每次你可以从S的开头或者结尾取出一个字符,放到一个T字符串的尾部
输出字典序最小的T字符串,每80个字符换一行输出
总结
因为n\leq 2000,所以这道题贪心的过程中可以用一下朴素的暴力:
比较当前剩余队列里的字母,如果一样就往中间继续迭代,哪边最终的字母小就选哪边。
AC代码
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int n,l,r,ll,rr;
string a,b,ans;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
cin>>b;
a = a + b;
}
l=0;r=n-1;
while(l<r){
ll=l,rr=r;
while(ll<rr&&a[ll]==a[rr]){
ll++;rr--;
}
if(a[ll]<a[rr]){
ans=ans+a[l];
l++;
}else{
ans=ans+a[r];
r--;
}
}
ans=ans+a[r];
for(int i=0;i<n;i++){
cout<<ans[i];
if((i+1)%80==0&&i!=n-1){
cout<<endl;
}
}
}