上海计算机学会2024年9月月赛C++丙组T3穿插字符串
发布时间
阅读量：
阅读量
穿插字符串
内存限制: 256 Mb时间限制: 1000 ms
题目描述
两个字符串可以穿插合并成一个字符串。规则是不断地提取两个字符串的首字母，直到两个字符串被取完为止，以提取的顺序合并成一个字符串。
比如 acac 与 bdbd 可以穿插成 abcdabcd，也可以穿插成 acbdacbd 或 bdacbdac。
给定两个字符串 s 与 t，s 由一部分英文字符构成，t 由另一部分英文构成，请将它们穿插合并成一个字典序意义下最小的字符串。
所谓字典序，是指两个字符串比较大小的方法：
- 空串是最小的字符串；
- 对于两个不为空的字符串，如果首字母不同，则首字母较小的字符串更小；
- 否则，以去掉首字母后剩余的字符串的字典序为准。
输入格式
- 第一行：一个字符串表示 s
- 第二行：一个字符串表示 t
- 保证 s 与 t 只包含小写字母，且 t 的字符与 s 完全不同。
输出格式
- 第一行：一个字符串表示 s 与 t 穿插后形成的最小字符串。
数据范围
记 s 的长度为 ∣s∣
- 30% 的分数，1≤∣s∣,∣t∣≤100
- 60% 的分数，1≤∣s∣,∣t∣≤10,000
- 100% 的分数，1≤∣s∣,∣t∣≤100,000
样例数据
输入:
acca
bbdd
输出:
abbccadd
解析：类似归并算法，将两个字符串中较小的字母优先插入，详见代码：
#include<bits/stdc++.h>
using namespace std;
string s, t;
int main() {
cin >> s >> t;
//两个字符串都从头开始，都到尾结束
for(int i = 0, j = 0; i < s.length() || j < t.length();) {
if (i < s.length() && j < t.length()) { //都没到尾
if (s[i] <= t[j]) { //s小，s上
cout << s[i];
i++;
} else { //否则就是t小，t上
cout << t[j];
j++;
}
} else if (i < s.length()) { //如果只有s没到尾，s上
cout << s[i];
i++;
} else if (j < t.length()) { //如果只有t没到尾，t上
cout << t[j];
j++;
}
}
return 0 ;
}
全部评论 (0)
还没有任何评论哟~