Problem #3038 - ECNU Online Judge

10175102262 LarsPendragon

6 年，4 月前

注意一点：当字符串第一个字符和最后一个字符相等时，应该比较其内侧的字符，先输出内侧字符更小一侧的字符。附C代码：

#include <stdio.h>
int main()
{
    int T, I;
    scanf("%d",&T);
    for(I=0; I<T; I++)
    {
        int cnt=0, l, i=0, j;
        char s[510];
        scanf("%d\n%s",&l,s);
        printf("case #%d:\n",I);
        for(j=l-1; cnt<l;)
        {
            if(s[i]<s[j]) printf("%c",s[i++]);
            else if(s[i]>s[j]) printf("%c",s[j--]);
            else
            {
                int k=1;
                for(;s[i+k]==s[i-k];k++);
                if(s[i+k]<s[j-k]) printf("%c",s[i++]);
                else printf("%c",s[j--]);
            }
            cnt++;
        }
        printf("\n");
    }
    return 0;
}

回复 4 0

Gottfried_Leibniz

4 年，2 月前

本题所给的字符串长度都过小，其实还可以利用单调性再优化，以达到$O(n)$复杂度(否则更大的数据朴素贪心是会TLE的)

回复 0 0

SNORLAX

4 年，3 月前

这题数据太水了居然可以直接水过去。

回复 0 0

computerLearner

3 年，4 月前

赞同, 题目只设计了第判断这个同值的一层次判断. 没有下狠心来个n层的判断

回复 0 0

zxCoder

4 年前

这题的正解呢？

回复 0 0

Fifnmar

4 年，4 月前

的确是贪心法的例题。

string lexmin(string_view str) {
    if (str.size() == 1) {
        return {str.begin(), str.end()};
    } else if (str.size() == 2) {
        if (str.front() > str.back()) {
            return {str.rbegin(), str.rend()};
        } else {
            return {str.begin(), str.end()};
        }
    } else {
        if (str.front() > str.back()) {
            return str.back() + lexmin(str.substr(0, str.size() - 1));
        } else if (str.front() < str.back()) {
            return str.front() + lexmin(str.substr(1, str.size() - 1));
        } else {
            auto a = lexmin(str.substr(1, str.size() - 1));
            auto b = lexmin(str.substr(0, str.size() - 1));
            return str.front() + (a < b ? a : b);
        }
    }
}

int main() {
    u32 t; cin >> t;
    for (u32 i = 0; i < t; ++i) {
        u32 n; cin >> n;
        string str; cin >> str;
        cout << "case #" << i << ":\n";
        cout << lexmin(str) << '\n';
    }
}

回复 0 0

Fifnmar

4 年，4 月前

我写得有点冗长了。

回复 0 0

你当前正在回复 博客/题目