刷题与ZZ错误记录14

POJ-3617 Best Cow Line

题面

【VJudge】 【POJ】

多组测试数据
给你一个长度为N的字符串S,输入格式是依次输入N个字符
N <= 2000
每次你可以从S的开头或者结尾取出一个字符,放到一个T字符串的尾部
输出字典序最小的T字符串,每80个字符换一行输出

总结

因为n\leq 2000,所以这道题贪心的过程中可以用一下朴素的暴力:

比较当前剩余队列里的字母,如果一样就往中间继续迭代,哪边最终的字母小就选哪边。

AC代码

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int n,l,r,ll,rr;
string a,b,ans;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        cin>>b;
        a = a + b;
    }
    l=0;r=n-1;
    while(l<r){
        ll=l,rr=r;
        while(ll<rr&&a[ll]==a[rr]){
            ll++;rr--;
        }
        if(a[ll]<a[rr]){
            ans=ans+a[l];
            l++;
        }else{
            ans=ans+a[r];
            r--;
        }
    }
    ans=ans+a[r];
    for(int i=0;i<n;i++){
        cout<<ans[i];
        if((i+1)%80==0&&i!=n-1){
            cout<<endl;
        }
    }
}

页面: 1 2 3 4 5 6 7

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注