一道贪心，但错了90%

Question

有一个字符串S，S的每个字符都是小写字母。有N个贴纸，第i个贴纸上面印有一个字符ch[i]。使用1个贴纸可以替代S的1个字符。例如你可以使用第i个贴纸去替代S的第j个字符，即把S[j]替换成ch[i]。注意：贴纸只能用来替换S的字符，贴纸不能增加或减少S的长度。你的目标是使得S的字典序最大，输出能得到的字典序最大是S。
输入
多组测试数据。
第一行，一个整数G，表示有G组测试数据。1<=G<=10。
每组测试数据格式：
第一行，一个字符串S，S的长度不超过50。
第二行，一个整数N。1<=N<=50。
第三行，N个字符，第i个字符是ch[i]。

输出
共G行，每行一个字符串。
样例输入 Copy
1
xx
2
yz
样例输出 Copy
zy
[提交][状态]
错误代码：

#include<bits/stdc++.h>
#define MX 362980
using namespace std;
bool cmp(char &x,char &y)
{
    return x > y;
}
int main()
{
    int T,n,i,j;
    cin >> T;
    while(T--)
    {
        char s[MX + 10],ch[MX + 10];
        cin >> s >> n;
        cin >> ch;
        int len = strlen(s),lench = strlen(ch);
        sort(ch,ch + lench,cmp);
        for (i = 0;i < lench;i++)
        {
            if (i >= len)
            {
                break;
            }
            if (s[i] < ch[i])
            {
                cout << ch[i];
            }
            else
            {
                cout << s[i];
            }
        }
        if (lench < len)
        {
            for (i = lench;i < len;i++)
            {
                cout << s[i];
            }
        }
        cout << endl;
    }
    return 0;
}

Answer 1

该回答引用自GPT-3.5,由博主GISer Liu编写：

这个问题的核心是要通过贴纸来替换字符串S中的字符，使得替换后的字符串字典序最大。这是一个贪心算法的问题。
首先，我们对贴纸上的字符按照字典序进行排序，这样可以确保在替换时选择最大的字符。
接着，我们从字符串S的第一个字符开始，逐个检查是否存在可以替换的贴纸字符。如果存在可以替换的字符，我们就替换成贴纸中最大的字符，然后继续向后检查。如果不存在可以替换的字符，或者贴纸已经用完，就直接输出剩下的字符串。
下面是对应的代码：
cpp
Copy code

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
bool cmp(char &x, char &y) {
return x > y;
}
int main() {
int T;
cin >> T;
while (T--) {
char s[55], ch[55];
cin >> s;
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> ch[i];
}
int len = strlen(s);
sort(ch, ch + n, cmp); // 按字典序降序排序贴纸字符
int j = 0; // 贴纸的索引
for (int i = 0; i < len; i++) {
if (j < n && ch[j] > s[i]) { // 贴纸可用且贴纸字符比原字符串字符大
cout << ch[j++];
} else {
cout << s[i]; // 直接输出原字符串字符
}
}
cout << endl;
}
return 0;
}

修改的部分包括：

1. 在排序贴纸字符时，改为按照字典序的逆序排列，确保选择的贴纸字符尽可能大。
2. 在替换字符时，如果贴纸已经用完，需要继续输出原字符串中剩余的字符。
   这样，就能够得到符合要求的结果了。

如果该回答解决了您的问题，请采纳！如果没有，请私信联系或评论您的疑惑