BZOJ 1640/1692 : [Usaco2007 Nov]Best Cow Line 队列变换 (贪心)
1640: [Usaco2007 Nov]Best Cow Line 队列变换
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 710 Solved: 373 [Submit][Status][Discuss]
Description
FJ打算带着他可爱的N (1 ≤ N ≤ 2,000)头奶牛去参加”年度最佳老农”的比赛.在比赛中,每个农夫把他的奶牛排成一列,然后准备经过评委检验. 比赛中简单地将奶牛的名字缩写为其头字母(the initial letter of every cow),举个例子,FJ带了Bessie, Sylvia,和Dora,那么就可以缩写为BSD. FJ只需将奶牛的一个序列重新排列,然后参加比赛.他可以让序列中的第一头奶牛,或者最后一头走出来,站到新队列的队尾. 利欲熏心的FJ为了取得冠军,他就必须使新队列的字典序尽量小. 给你初始奶牛序列(用头字母)表示,然后按照上述的规则组成新序列,并使新序列的字典序尽量小.
Input
第1行:一个整数N.
第2行至第N+1行:每行一个大写字母,表示初始序列中该奶牛的头字母.
Output
得到的最小字典序的序列.每输出80个字母需要一个换行!
Sample Input
6 A C D B C B
Sample Output
ABCBCD
HINT
Source
思路：比较麻烦的一个贪心。。对拍才找出了一个错误。。。
写丑了QAQ
/* ***********************************************
Author :111qqz
Created Time :2016年04月08日 星期五 16时16分34秒
File Name :code/bzoj/1640.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=2E3+7;
7int n;
8int a[N];
9string ans;
10int main()
11{
12 #ifndef ONLINE_JUDGE
13 freopen("code/in.txt","r",stdin);
14 #endif
1 ios::sync_with_stdio(false);
2 cin>>n;
3 ans ="";
4 for ( int i = 1 ;i <= n ; i++)
5 {
6 char ch;
7 cin>>ch;
8 a[i] = ch-'A'+1;
9 }
int l = 1;
int r = n ;
1 while (l<=r)
2 {
3 if (l==r)
4 {
5 // cout<<"aans:"<<ans<<endl;
6 ans += char(a[l]+64);
7 // cout<<"aaans:"<<ans<<endl;
1 break;
2 }
3 if (a[l]!=a[r])
4 {
5 if (a[l]<a[r])
6 {
7 ans += char(a[l]+64);
8 l++;
9 }
10 else
11 {
12 ans += char(a[r]+64);
13 r--;
14 }
15 }
16 else
17 {
18 if (l==r) continue;
19 int tmpl = l;
20 int tmpr = r;
21 while (a[tmpl]==a[tmpr]&&tmpl<tmpr)
22 {
23 tmpl++;
24 tmpr--;
25 }
26// cout<<"tmpl:"<<tmpl<<" tmpr:"<<tmpr<<" ans:"<<ans<<endl;
27 if (tmpl>=tmpr)
28 {
29 while (l<=r)
30 {
31 // cout<<"l:"<<l<<" r:"<<r<<" ans:"<<ans<<endl;
1 if (a[l]<=a[r])
2 {
3 ans += char(a[l]+64);
4 l++;
5 break;
6 }
7 else
8 {
9 ans += char(a[r]+64);
10 r--;
11 break;
12 }
13 //cout<<" ans:"<<ans<<endl;
14 }
15 /* for ( int i = l ; i <= r ; i++)
16 {
17 if (tmpl==tmpr&&a[tmpl]>a[l]&&i==tmpl) continue;
18 ans +=char(a[i]+64);
19 }
20 if (tmpl==tmpr&&a[tmpl]>a[l]) ans += char(a[tmpl]+64); */
21 //break;
22 }
23 else
24 {
25 while (l<tmpl&&r>tmpr)
26 {
27 // cout<<"l:"<<l<<" r:"<<r<<" anssss:"<<ans<<endl;
1 if (a[l]==a[r])
2 {
3 if (a[tmpl]<=a[tmpr])
4 {
5 ans += char(a[l]+64);
6 l++;
7 break;
8 }else
9 {
10 ans += char(a[r]+64);
11 r--;
12 break;
13 }
1 }
2 else
3 {
1 if (a[l]<a[r])
2 {
3 ans+=char(a[l]+64);
4 l++;
5 break;
6 }
7 else
8 {
9 ans+=char(a[r]+64);
10 r--;
11 break;
12 }
13 // cout<<"l:"<<l<<" r:"<<r<<" anssss:"<<ans<<endl;
14 }
15 }
16 /* if (a[tmpl]<a[tmpr])
17 {
18 for ( int i = l ; i <= tmpl ; i++) ans +=char(a[i]+64);
19 l = tmpl+1;
20 }
21 else
22 {
23 for ( int i = r ; i >= tmpr ; i--) ans +=char(a[i]+64);
24 r = tmpr-1;
25 } */
26 }
27 }
28 // cout<<"l:"<<l<<" r:"<<r<<" ans:"<<ans<<endl;
1 }
2 int len = ans.length();
3 for ( int i = 0 ; i < len ; i++)
4 {
5 cout<<ans[i];
6 if ((i+1)==0) cout<<endl;
7 }
8// cout<<ans<<endl;
9 #ifndef ONLINE_JUDGE
10 fclose(stdin);
11 #endif
12 return 0;
13}
出错数据：
input:
393
A
C
A
A
B
C
C
C
C
B
B
C
A
C
C
C
B
B
A
C
C
B
C
C
C
C
A
A
A
A
C
A
A
A
B
C
C
C
B
A
A
B
A
A
B
C
C
C
A
A
C
A
C
A
C
B
C
C
B
A
A
B
C
B
B
A
B
B
C
A
B
A
B
B
B
B
B
B
A
B
A
B
A
C
B
A
B
B
B
A
B
C
C
A
B
B
C
C
A
B
C
C
A
C
C
B
A
A
A
A
A
A
B
A
A
A
B
C
B
C
A
A
C
A
B
A
B
A
C
C
A
C
C
A
B
C
C
B
C
C
A
A
B
C
B
B
A
A
B
B
A
B
C
C
C
C
A
C
A
A
B
A
A
B
B
B
A
A
A
B
B
B
B
C
A
A
B
B
B
A
A
B
B
A
C
C
C
C
B
A
A
A
B
A
C
B
B
A
C
C
B
A
A
B
A
C
C
C
A
A
C
B
C
C
C
B
B
C
B
C
A
B
C
A
C
C
B
A
A
A
B
C
C
C
B
C
B
A
A
C
B
C
A
C
B
A
A
C
B
B
C
B
A
A
C
C
C
A
B
A
C
A
B
B
C
C
B
C
B
B
B
A
C
C
C
A
B
A
B
C
C
B
B
A
B
B
A
C
C
C
C
B
C
A
A
A
A
A
C
C
C
B
C
B
A
C
A
B
A
C
B
C
A
A
A
A
C
C
C
B
B
B
B
C
C
B
A
A
C
C
C
A
A
C
B
B
B
C
B
C
B
C
C
A
A
C
A
C
C
C
C
B
A
A
B
A
C
B
B
C
B
B
C
B
B
B
C
A
C
B
A
B
B
C
C
B
C
C
C
A
C
B
C
B
B
A
B
B
C
B
A
A
C
我的输出：ACAABCBBABBCAABCBCACCCBCCBBABCACBBBCBBCBBCABAABCCCCACAACCBCBCBBBCAACCCAABCCBBBBC
CCAAAACBCABACABCBCCCAAAAACBCCCCABBABBCCBABACCCABBBCBCCBBACABACCCAABCBBCAABCACBCA
ABCBCCCBAAABCCACBACBCBBCCCBCAACCCABAABCCABBCABAAABCCCCABBAABBBAACBBBBAAABBBAABAA
CACCCCBABBAABBCBAACCBCCBACCACCABABACAACBCBAAABAAAAAABCCACCBACCBBACCBABBBABCABABA
BBBBBBABACBBABBCBAABCCBCACACAACCCBAABAABCCCBAAACAAAACCCCBBCACCCBBACCBCCCC
正确输出：ACAABCAABCBBABBCBCACCCBCCBBABCACBBBCBBCBBCABAABCCCCACAACCBCBCBBBCAACCCAABCCBBBBC
CCAAAACBCABACABCBCCCAAAAACBCCCCABBABBCCBABACCCABBBCBCCBBACABACCCAABCBBCAABCACBCA
ABCBCCCBAAABCCACBACBCBBCCCBCAACCCABAABCCABBCABAAABCCCCABBAABBBAACBBBBAAABBBAABAA
CACCCCBABBAABBCBAACCBCCBACCACCABABACAACBCBAAABAAAAAABCCACCBACCBBACCBABBBABCABABA
BBBBBBABACBBABBCBAABCCBCACACAACCCBAABAABCCCBAAACAAAACCCCBBCACCCBBACCBCCCC