poj3617字典序+贪心

poj3617 在白书上看见的一题,算是字典序和贪心的一个混合吧
没图放
题目链接:http://poj.org/problem?id=3617

最好的牛线
时间限制: 1000MS 内存限制: 65536K
提交总数: 32600 接受: 8643
描述

FJ即将把他的ñ(1≤ ñ ≤2000)奶牛竞争一年一度的“年度农民”。在这场比赛中,每个农民都将他的奶牛排成一排,然后将他们赶到评委面前。

比赛组织者今年采用了一种新的注册方案:只需按照它们出现的顺序注册每头奶牛的首字母(即,如果FJ按照该顺序选择Bessie,Sylvia和Dora,他只需注册BSD)。在注册阶段结束后,根据奶牛姓名首字母的字符串判断每个组的字典顺序增加。

FJ今年很忙,不得不赶回他的农场,所以他希望尽早接受评判。在登记之前,他决定重新安排已经排队的奶牛。

FJ标志着竞争奶牛新品系的位置。然后,他通过反复将原始线的(剩余部分)中的第一头或最后一头母牛发送到新线的末端,继续将奶牛从旧线编组到新线。当他完成后,FJ带着他的奶牛在这个新订单中注册。

鉴于他的奶牛的初始顺序,确定他可以这样做的最少词典的首字母串。

输入

第1行:单个整数:N 第2行.N +1:第i + 1行包含原始行中第i个位置的母牛的单个初始(’A’..’Z’)

产量

他可以制作的字典最少的字符串。每一行(除了最后一行)在新行中包含80个母牛(’A’..’Z’)的首字母。

样本输入

6
一个
C
d

C

样本输出

ABCBCD
资源

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
using namespace std;
int main(){
//ios::sync_with_stdio(false);
int n;
string s,t;
cin>>n;
for(int i=0;i<n;i++)
cin>>s[i];
int l=0,r=n-1;
int ans=0;
while(l<=r){
ans++;
bool left=false;
for(int i=0;i<n;i++){
if(s[l+i]<s[r-i]){
left=true;
break;
}
else if(s[l+i]>s[r-i]){
left=false;
break;
}
}
if(left)cout<<s[l++];
else cout<<s[r--];
if(ans%80==0)cout<<endl;
}

cout<<endl;
return 0;
}

对了 ios::sync_with_stdio(false);在poj不好使,会RE

coswindy

-------------本文结束感谢您的阅读-------------