首页 > 试题广场 >

迷途之家的大贤者

[编程题]迷途之家的大贤者

热度指数：1302 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小红在穿越后不久，就被大贤者小紫发现了，于是小紫友好地请小红来迷途之家做客。
小红和小紫在迷途之家玩一个游戏：
两人拿到了一个字符串，小红首先操作一次，选择一个子串删除（可以删除空串，也就是相当于不操作）；然后小紫继续操作一次，选择一个子串删除（可以删除空串，也就是相当于不操作）。之后得到一个最终的字符串，小红希望这个字符串的字典序尽可能大，小紫希望这个字符串的字典序尽可能小。但是请注意，两个人操作都不能选择整个字符串删除，即不能形成空串。
小紫作为东道主，非常大度的让小红先手进行游戏。
小红想知道，双方都采取最优策略时，最终生成的字符串是什么？

输入描述:

第一行输入一个正整数，代表字符串长度。
第二行输入一个长度为的，仅包含小写字母的字符串。

输出描述:

最终生成的字符串。

示例1

输入

6
arcaea

输出

说明

小红删除子串"arc"形成"aea"，然后小紫删除子串"ea"形成"a"。可以证明，小红无论第一轮怎么删除，小紫都可以生成字符串"a"，显然是字典序最小的。

算法知识视频讲解

Yui___

猜到了

#include <iostream>
#include <string>

int main()
{

    int n = 0;
    std::cin>>n;

    std::string s;
    std::cin>>s;
    std::cout<<(s[0] > s.back() ? s[0] : s.back());

}

发表于 2025-11-28 16:30:40 回复(0)

Reisentyan

注意到，小红不论想以哪一个大字符开头，小紫都会使得答案变小，唯独只有一个字符时，答案无法变小

小红不可能使得开头的字符很小，这样答案会劣

就算整个字符串只有一种字符，那么小红把字符缩短，答案也会变劣

证明，为什么答案只有一个字符
假设最终答案，字符有两个，且大小关系为：大大，小小，大小，小大
第一种情况被排除，因为小紫一定会删掉一个大的

第二种情况排除，同理

第三种情况排除，小紫不会留下一个大的

第四种情况，同理

所以最终，只有一个字符的情况，那么选谁呢?

小红显然可以删除字符串，使得只有第一个或者最后一个字符

这样小紫不可能把答案变坏

难道答案不可能是中间的字符吗？

由于小红不管删除哪一段，小紫都可以找到剩下的字符中，最小的那一个，使之作为开头

也就是说，如果小红不把第一个字符或者最后一个字符作为答案的话，那么答案一定会变得比第一个或者最后一个更劣

假设：

adbbc

小红如何才能使得答案为d，显然不可能

会不会有这样的情况，小红选取一段比较特别的段，使得小紫无论如何，最小的答案长度都为2？

假设小红选取完了之后，剩下的一段为dab，小紫一定会删掉d，使得答案为ab

那么小红不可能会使得剩下的一段为dab，原本字符串可能如下：

???dab
d???ab

da???b

dab???

小红还不如直接选保留d，或者保留b

发表于 2025-11-28 22:14:26 回复(0)

Java

牛客203596504号

首尾两个字符哪个大就剩哪个。来个Java版答案。

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        in.nextLine();
        char[] text = in.nextLine().toCharArray();
        System.out.println(text[0] > text[text.length - 1] ?
                           text[0] : text[text.length - 1]);
    }
}

发表于 2025-11-28 19:08:11 回复(0)

王子默25软工03B20250304311

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <stdbool.h>

#include <limits.h>

#include <math.h>

#define ll long long

#define MOD 1000000007

#define inv2 500000004

int cmp(const void *a, const void *b)

{

return *(int *)a - *(int *)b;

}

int main()

{

int n;

scanf("%d", &n);

char* s = malloc(sizeof(char) * n);

scanf("%s", s);

printf("%c", s[0] > s[n - 1] ? s[0] : s[n - 1]);

}

发表于 2025-11-28 18:35:17 回复(0)

提交观点

问题信息

难度：

4条回答 7收藏 96浏览

迷途之家的大贤者

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题