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

prefer · 2018-10-30 15:47:09 · 题解

题目做法：从当前字符串最前面，最后面选一个字典序较小的然后拉到一个新的字符串序列中，如果相同就一直往中间扫描直到发现不同为止（一个字符如果被选中之后那么就不可以再次选择了），所以我们左右各设一个指针扫描就好了，不需要递归。

#include<bits/stdc++.h>
using namespace std;
inline int read() {
    int ret=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9') {
        if (ch=='-') f=-f;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
char a[200005],ans[200005];
int main() {
//  freopen("bcl.in","r",stdin);
//  freopen("bcl.out","w",stdout);
    int n=read();
    for(int i=1; i<=n; i++)a[i]=read();
    int j=n;
    int i=1;
    int o=1;//o为选中之后的序列的编号
    while(o<=n) {//o<=n意味着没有选完
        if(a[i]<a[j]) {//如果输入的字符串当前head小于tail
            ans[o]=a[i],i++,o++;//我们的左边就被选择了，此时左指针++，选中序列之后的编号++
            continue;
        }
        if(a[i]>a[j]) {//与上述类似
            ans[o]=a[j],j--,o++;
            continue;
        } else if(a[i]==a[j]) {//如果相同
            int ii=i+1;//用于此处比较的左指针
            int jj=j-1;//用于此处比较的右指针
            while(jj-ii>1&&a[ii]==a[jj]) {//不越界并且仍然相同
                ii++;
                jj--;
            }//不相同的时候就退出了
            if(a[ii]<a[jj]) {//比较方法与之前类似
                ans[o]=a[i],i++;
            } else ans[o]=a[j],j--;
            o++;//又选了一个，o++
        }
    }
    int jishuqi=0;//换行
    for(int i=1; i<=n; i++) {
        if(jishuqi==80) {//如果jishuqi为80说明已经输出了80个字符了
            printf("\n");//换行
            jishuqi=0;
        }
        cout<<ans[i];//输出
        jishuqi++;
    }
    return 0;
}