[BZOJ1640]&&[Usaco2007 Nov]Best Cow Line 队列变换

2014-07-01
竞赛题解 / 贪心
BZOJUSACO

描述 Description

FJ 打算带着他可爱的 N (1 ≤ N ≤ 2,000)头奶牛去参加”年度最佳老农”的比赛. 在比赛中, 每个农夫把他的奶牛排成一列, 然后准备经过评委检验. 比赛中简单地将奶牛的名字缩写为其头字母 (the initial letter of every cow), 举个例子, FJ 带了 Bessie, Sylvia, 和 Dora, 那么就可以缩写为 BSD. FJ 只需将奶牛的一个序列重新排列, 然后参加比赛. 他可以让序列中的第一头奶牛, 或者最后一头走出来, 站到新队列的队尾. 利欲熏心的 FJ 为了取得冠军, 他就必须使新队列的字典序尽量小. 给你初始奶牛序列(用头字母) 表示, 然后按照上述的规则组成新序列, 并使新序列的字典序尽量小.

输入格式 InputFormat

第 1 行: 一个整数 N.

第 2 行至第 N+1 行: 每行一个大写字母, 表示初始序列中该奶牛的头字母.

输出格式 OutputFormat

得到的最小字典序的序列. 每输出 80 个字母需要一个换行!

样例输入 SampleInput

51
A
A
B
B
A
B
B
B
B
A
B
A
B
B
A
B
A
B
A
A
B
B
A
A
B
B
B
A
A
A
A
B
A
A
B
A
B
A
A
B
B
A
A
A
B
B
B
B
B
B
A

样例输出 SampleOutput

AAABBABBBBABABBABABAABBAABBBAAAABAABABAABBAAABBBBBB

来源 Source

Silver

BZOJ 1640

代码 Code

每次从两边取较小的，若相同，则往下一位比较，直到找到一个较小的，取较小的那边的。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
char a[2005];
int i,j,t,n,m,l,r,k,z,y,x;
inline char read()
{
    char ch=getchar();
    while (ch<'A' || ch>'Z') ch=getchar();
    return ch;
}
inline bool comp(int l,int r)
{
    if (l==r) return true;
    while (a[l]==a[r] && l<r) l++,r--;
    return a[l]<a[r];
}
int main()
{
    scanf("%d",&n);
    for (i=1;i<=n;i++) a[i]=read();
    l=1;r=n;
    t=0;
    while (l<=r)
    {
        if (comp(l,r))
        {
            printf("%c",a[l++]);
            t++;
        }
        else
        {
            printf("%c",a[r--]);
            t++;
        }
        if (t==80)
        {
            printf("n");
            t=0;
        }
    }
    return 0;
}