题解 P6140 【[USACO07NOV]Best Cow Line S】

· · 题解

好久没发过题解了，正好这题是晚上模拟赛的一题，就来写一写咯。

这一题看上去显然是贪心，我们设两个指针，a 表示头指针，也就是队列首端， b 表示为指针，也就是队列末端。

下面是最好容易想到的策略：

  1. 当 \text{s[a]>s[b]} ，我们肯定是会选 \text {s[b]} ，随之 b- - 。
  2. 当 \text{s[a]<s[b]} ，我们肯定是会选 \text {s[a]} ，随之 a++ 。

但是，通过样例我们发现，会出现 \text {s[a]==s[b]} 情况，这种情况该怎么处理呢？

其实也很简单，我们找距离 \text {s[a]} 和 \text {s[b]} 最近的且不等于 \text {s[a或b]} 的字符，再比较它们大小即可。

\text {Code}: 
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
char s[3010];
int n,i,a,b,j,p,q;
int main () {
    scanf ("%d",&n);
    for (i=1;i<=n;i++)
        cin>>s[i];
    a=1;
    b=n;
    for (i=1;i<=n;i++) {//从i开始枚举。
        for (j=i;j<=i+79&&j<=n;j++) {//每80个字符就换行。
            if (s[a]==s[b]) {
                p=a;
                q=b;
                while (s[p]==s[q]) {
                    p++;
                    q--;
                }//策略3。
                if (s[p]<=s[q]) {
                    printf ("%c",s[a]);
                    a++;
                } //这里又可以想到上面最简单的两种策略。
                else {
                    printf ("%c",s[b]);
                    b--;
                }
            }
            else {
                if (s[a]>s[b]) {
                    printf ("%c",s[b]);
                    b--;//策略1。
                } 
                else {
                    printf ("%c",s[a]);
                    a++;//策略2。
                }
            }
        }
        i+=79;//继续搜索下面的80个字符。
        puts ("");
    }
    return 0;
}