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

cold_cold · 2018-03-10 01:43:17 · 题解

• 长度为N的字符串S，要让你构造一个字符串T，你可以每次在S中删去头部一个字符，加到T中，也可以在S的尾部删去一个字符加到T中，问你T的字典最小的答案是什么
• 挑S的头和尾部字典序列最小的字符
• 如果相等那么就继续向下一层挑S的次头和次尾部字典序列最小的字符

#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstring>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
using namespace std;
int n,ji=0;
char a[30100];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        getchar(),scanf("%c",&a[i]);
    int h=1,t=n;
    while(h<t)
    {
        if(a[h]<a[t])
            printf("%c",a[h++]);
        else if(a[h]>a[t])
            printf("%c",a[t--]);
        else
        {
            int x=h,y=t;
            while(x<y&&a[x]==a[y])
                x++,y--;
            if(a[x]<a[y])
                printf("%c",a[h++]);
            else
                printf("%c",a[t--]);
        }
        ji++;
        if(ji==80)
            printf("\n"),ji=0;
    }
    printf("%c",a[h]);
    return 0;
}