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

· · 题解

这道题目其实很简单，就是贪心！！！

贪心过程： 假设 l为只想最左边的数，r为指向最右边的数，从两边比较。

若a[ l ]<a[ r ];l++; 若a[ r ]>a[ l ];r--；

若a[ l ]==a[ r ];则check：

做一次循环，l每次加1，r每次减1； 若a[ l ]<a[ r ] return 1；

否则 return 0；

还有一种玄学，就是设一个flag记录不同的字母的个数01，如果flag为1，直接输出！！！

CODE：

#include<bits/stdc++.h>
using namespace std;
int n,l,r,t=0;
bool b[30001];
char a[30001],ans[30001];
inline bool check(int l,int r){
    int j=r-1;
    for(register int i=l+1;i<=r;i++){
        int x=a[i],y=a[j];
        if(x<y) return 1;
        if(y<x) return 0;
        j--; 
    }
}
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;
}
int main(){
    scanf("%d",&n);
    int flag=-1;
    for(register int i=1;i<=n;i++){
        a[i]=getchar();
        while(a[i]<'A'||a[i]>'Z') a[i]=getchar();
        if(!b[a[i]]) b[a[i]]=1,flag++;
    }
    if(flag==1){
        for(register int i=1;i<=n;i++){
            putchar(a[i]);
            if(i%80==0)putchar('\n');
    }
        return 0;
    }
    l=1;r=n;
    while(l<=r){
        int x=a[l],y=a[r];
        if(x<y) ans[++t]=x,l++;
        if(x>y) ans[++t]=y,r--;
        if(x==y){
            if(check(l,r)==1) l++,ans[++t]=x;
            else r--,ans[++t]=y;
        }
    }
    for(register int i=1;i<=n;i++){
        putchar(ans[i]);
        if(i%80==0) putchar('\n');
    } 
    return 0;
}

码风奇丑，请多指教！！！