题目大意:
给定两个由小写字母构成的字符串 $s1$,$s2$。
现在,请你生成一个新字符串 $s3$,要求 $s3=s^′_1+s^′_2$ 且 $s3$ 的字典序尽可能小。
$s^′_1$ 是指 $s1$ 的非空前缀,$s^′_2$ 是指 $s2$ 的非空前缀。
解题思路:
首先给大家说一下什么是非空前缀。
就相当于从一个字符串中截取一段字符串,这个字符串必须从整个字符串的开头开始截取,也就是说:
abcdef
所有的非空前缀有:
a,ab,abc,
abcd,abcde,abcdef
然后我们直接枚举两个字符串从前面取出来的前缀,组合起来然后求最小值即可。
完整代码,时间复杂度:$O(n^2)$
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
string a, b;
string ans = "zzzzzzzzzzzzzzzzzzzzzzzzzzzz";
//先赋值为“无穷”,准备取最小。
int main()
{
cin >> a >> b;
for (int i = 1; i <= a.size(); i ++ ) {
for (int j = 1; j <= b.size(); j ++ ) { //枚举两个字符串截取前缀的长度,不能为0。
string c = a.substr(0, i) + b.substr(0, j);//第一个参数是起始位置,第二个是长度。
ans = min(ans, c); //更新答案
}
}
cout << ans << endl;
return 0;
}
%%%
感觉三个代码(帖主,stotue,yxc)挺像的
哈哈,都是同样的思路
懂了
感觉代码差不多,但是他提交时间似乎要早一点
如果冒犯到了您,我很抱歉
考试的时候是没法看别人代码的,所以应该不是抄的
草怎么我们都赋值的一堆
z
(哈哈哈
大佬,我不理解第一题为啥答案s1要尽可能长,题目只说字典序要尽量小,要是小的话那就只要第一个字符串的第一个和第二个字符串的第一个不就行了吗
是s1尽可能长,要s2的第一个即可
为啥s1要尽可能长
字典序小就只要俩字母不行吗
我没说要尽可能长呀
答案看起来是s1尽可能长
你好像没理解字典序的含义,aab是小于ab的
“看起来”
这是在一定条件基础上
字典序是按位比较的??
懂了,我是字典序理解错了
牛啊
好耶