题解 P2870 【[USACO07DEC]最佳牛线，黄金Best Cow Line, Gold】

NaVi_Awson · 2017-02-06 10:50:07 · 题解

本人蒻蒟，一种比较笨的方法，能过

从字典序性质来看，无论字符串末尾有多大，只要保证前面部分较小就可以

比较队首，队尾，小的直接输出

相等比较麻烦

附上的程序比较暴力（其实还可以优化）

每次相等时，往里面搜，找到一个能够比出大小的便输出

再加个判断：如果当前字母为序列中最小元素，直接输出

附上代码，必要时有注解：

#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
int n;
char a[30005];
int num[500];//保存每个字母出现次数
int l,r;
char minc;
int main()
{
    scanf("%d",&n);
    getchar();
    for (int i=1; i<=n; i++)
    {
        scanf("%c",&a[i]);
        num[a[i]]++;
        getchar();
    }
    for (int i='A'; i<='Z'; i++)
        if (num[i]!=0)//求出出现最小字母
        {
            minc=i;
            break;
        }
    l=1;
    r=n;
    for (int i=1; i<=n; i++)
    {
        if (num[minc]==0)//若最小字母已输出完，再找次小
        {
            for (int j=minc; j<='Z'; j++)
                if (num[j]!=0)
                {
                    minc=j;
                    break;
                }
        }
        if (a[l]<a[r]||a[l]==minc)//之前所说的判断
        {
            num[a[l]]--;
            putchar(a[l]);
            l++;
        }
        else if (a[l]>a[r])
        {
            putchar(a[r]);
            num[a[r]]--;
            r--;
        }
        else if (a[l]==a[r])
        {
            int j;
            for (j=1; j<=(n-i+1)/2; j++)
            {
                if (a[l+j]<a[r-j])
                {
                    putchar(a[l]);
                    num[a[l]]--;
                    l++;
                    break;
                }
                else if (a[l+j]>a[r-j])
                {
                    putchar(a[r]);
                    num[a[r]]--;
                    r--;
                    break;
                }
            }
            if (j>(n-i+1)/2)
            {
                    putchar(a[l]);
                    num[a[l]]--;
                    l++;
            }
        }
        if (i%80==0) cout<<endl;
    }
    return;
}
代码做了些手脚，抄题解的注意了！！！