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

RainFestival · 2019-02-18 22:23:21 · 题解

这道题我们用一种比较特殊的方法

题目要求字典序最小

我们在序列两头找小的放就行了

当然这只是一个初步思路不然怎么是蓝题

问题

如果两头一样怎么办？？？

那么你就比较下一个，然后取下一个小的

如果下一个还一样继续比较

如果你这么写，将会收获一个TLE

所以要优化

我们先判断又回文，从第二个到中间一个都比前面大的

那就直接输出（玄学优化，从84->100）

下面是代码：

#include<iostream>
#include<cstdio>
using namespace std;
char ans[500005],a[500005];
int n,p=0,k=0,same=0;
int main()
{
    scanf("%d",&n);
    same=1;
    for (int i=1;i<=n;i++)
        while (1)
        {
            scanf("%c",&a[i]);
            if (a[i]!=a[i-1]&&a[i]>1) same=0;
            if (a[i]>='A'&&a[i]<='Z') break;
        }
    same=1; 
    for (int i=1;i<=n;i++) if (a[i]!=a[n-i+1]) same=0;
    for (int i=2;i<=n/2;i++) if (a[i]>a[i-1]) same=0;
    if (same)
    {
        for (int k=1;k<=n;k++)
        if (k%80==0) printf("%c\n",a[k]);
        else printf("%c",a[k]); 
        return 0;
    }

    int i=1,j=n;
    while (i<j)
    {
        if (a[i]>a[j])
        {
            p++;
            ans[p]=a[j];
            j--;
            //cout<<"> ";
        }
        else if (a[j]>a[i])
             {
                 p++;
                 ans[p]=a[i];
                 i++;
                 //cout<<"< ";
             }
             else
             {
                 int i1=i,j1=j,win=-1;
                 while (a[i1]==a[j1]&&i<j)
                 {
                     i1++;
                     j1--;  
                     if (i1>j1) break;
                     if (a[i1]>a[j1]/*&&a[j1]<=a[j]*/)
                     {
                         win=0;
                         break;
                     }
                     else if (a[i1]<a[j1]/*&&a[i1]<=a[i]*/)
                          {
                              win=1;
                              break;
                          }
                          //else if (a[i1]>a[i]&&a[j1]>a[j])
                               //{
                                   //win=2;
                                   //break;
                               //}
                               else continue;
                 }
                 //if (win==-1)
                 //{
                    //for (k=i;k<=j;k++)
                    //{
                        //p++;
                        //ans[p]=a[k];
                    //}
                    //cout<<"win=-1 ";
                    //break;
                 //}
                 if (win==-1)
                 {
                    p++;
                    ans[p]=a[i];
                    i++;
                 }
                 else if (win==0)
                      {
                          //for (k=j;k>=j1;k--)
                          //{
                          //    p++;
                          //    ans[p]=a[k]; 
                          //}
                          //j=j1-1;
                          p++;
                          ans[p]=a[j];
                          j--;
                          //cout<<"win=0 ";
                      }
                      else if (win==1)
                           {
                               //for (k=i;k<=i1;k++)
                               //{
                                   //p++;
                                   //ans[p]=a[k];
                               //}
                               //i=i1+1;
                               p++;
                               ans[p]=a[i];
                               i++;
                               //cout<<"win=1 ";
                           }
                           //else
                           //{
                            //   for (k=i;k<=i1-1;k++)
                            //   {
                             //        p++;
                             //        ans[p]=a[k];
                             //  }
                             //  for (k=j;k>=j1+1;k--)
                             //  {
                             //      p++;
                             //      ans[p]=a[k];
                              // }
                              // i=i1;
                             // j=j1;
                               //cout<<"win=2 ";
                           //}
             }
        //cout<<i<<" "<<j<<" ";
        //for (int k=1;k<=n;k++)
        //if (k%80==0) printf("%c\n",ans[k]);
        //else printf("%c",ans[k]);
        //cout<<endl;
    }
    if (p<n)
    {
        p++;
        ans[p]=a[i];
    }
    for (int k=1;k<=n;k++)
        if (k%80==0) printf("%c\n",ans[k]);
        else printf("%c",ans[k]);
    return 0;
}

时间2965ms,空间1532kb,代码长度4.12kb

这是我在洛谷上提交的几乎最长的代码（除了p4420）

谢谢大佬们的观赏