思路：贪心，双指针，但是最坏时间复杂度是O(nm)，会超时，只能拿一部分分。

优化：可以先将第二个字符串排序，然后用last变量记录上一个字符的插入位置，每一次都只可能插入到上一个字符的后面，所以从last之后开始遍历。时间复杂度可以优化到O(n+mlogm)。

值得注意的是，第二个字符串的字符应该插入到第一个字符串中严格大于它的字符前面，不能等于。例如：

输入：
5 3
apple
ppp

答案：appleppp
错误答案：appppple

正确代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>

using namespace std;
const int N = 200010;

int n, m;
string s1, s2;

void solve()
{
    cin >> n >> m;
    cin >> s1;
    cin >> s2;

    sort(s2.begin(), s2.end());
    //cout << s2 << endl;
    int j = 0, last = 0;
    while (j < m) {
        int i = last;
        while (s1[i] <= s2[j] && i < n + j) 
            i++;
        s1.insert(i, 1, s2[j]);
        last = i + 1;
        j++;
    }
    cout << s1 << endl;
}

int main()
{

    solve();

    return 0;
}