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

Silver

思路:比较麻烦的一个贪心。。对拍才找出了一个错误。。。

写丑了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