题目描述
味味很喜欢玩一个数字替换的游戏，数字替换游戏是这样的：给出一个 n 位正整数 a， 然后再给你一个长度为 m 的数字序列 b，味味可以用 b 中的一些数字与 a 中各个位置上的 数字进行一对一的交换（当然也可以选择不交换）。当然 b 中的每个位置上的数字最多只能 被使用一次。这个游戏的目的是经过一系列替换后，使 a 的数值达到最大。
味味很聪明，在位数不多的情况下，总能快速的求出最后 a 的最大数值，但是当 n 很 大时，味味就无能为力了，所以她希望会写程序的你帮助她快速的求解 a 最后能到达的那 个最大值。
输入
输入共包含三行。第一行两个用空格隔开的正整数 n，m。第二行一个正整数 a（a 的最高位必定不是 0）。第三行一个长度为 m 的数字序列 b。
输出
输出仅包含一行一个数值，表示 a 最大可能达到的数值（输出不能含前导0）。
样例输入 Copy
4 3 1024 010
样例输出 Copy
1124
提示
b 中的一个 1 和 a 中的第二位上的 0 进行交换。
对于 20%的数据 1≤n，m≤10
对于 50%的数据 1≤n，m≤2000
对于 100%的数据 1≤n，m≤100000
心得：
就分享一道题目吧，这道题目我也是由于不认真读题才导致多次更改，坐题之前一定要看好条件啊，这道题目首先给出了两个条件m， n代表着输入的两个字符串的长度，但是，由于粗心吧，我直接忘记使用这两个条件了， 直接当成整数输入肯定会错。
：第一遍错误代码（不想看的话可以直接蹦到最下面ac代码
#include#include #include #include using namespace std; bool cmp(int a, int b) { return a > b; } int main() { int n, m, i, j, k, num; char op[100100]; int a[100100], b[100010]; cin >> n >> m; scanf("%dn", &num); for (i = 0; i < m; i++) { op[i] = getchar(); } op[++i] = ' '; int len1 = strlen(op); //字符串的长度 for (i = 0; op[i] != ' '; i++) { b[i] = op[i] - '0'; } sort (b, b + j, cmp); int len2 = 0; //数字的长度 i = 0; while (num) { a[i++] = num % 10; num /= 10; //cout << num << endl; len2++; } //倒着循环比较； j = 0; for (i = len2 - 1; i >= 0; i--) { for (j = 0; j < len1; j++) { if (b[j] > a[i]) { a[i] = b[j]; b[j] = -1; break; } } } //cout << len1 << endl; int sum = 0; for (i = len2 - 1; i >= 0; i--) { sum = sum * 10 + a[i]; } printf("%d", sum); return 0; }
写的麻烦又麻烦，算是给各位提个醒吧；
接下来说一下这道题目的正确做法：输入两个字符串（直接用scanf就可以）
对第二个字符串用sort进行排序， 从大到小；
大小比较，大的话就把第二个赋值给第一个！！！！问题是这里要求每一个只能用一次，也就是说我们要想办法跳过去这一步，我感觉这个题我唯一写的比较节省时间的地方就是这里：
k = 0;
for (i = 0; i < m; i++) {
for (j = k; j < n; j++) {
if (bp[j] - '0' > op[i] - '0') {
k++;
op[i] = bp[j];
break;
} else {
break;
}
}
}
这里看似是两个循环，其实只有一个循环，里面的用k巧妙的避开了上一次使用过的数据，因为已经处理过了，而且只用比较一次，比较省事，也不会担心超时（我讨厌超时orz）
最后附上ac代码，本人能力有限，写这篇博客也是出于反思和总结，希望能帮到你们！
#include#include using namespace std; bool cmp(char a, char b) { return a - '0' > b - '0'; } char op[100010], bp[100010]; int main() { int m, n, i, j, k; cin >> m >> n; scanf("%s", op); scanf("%s", bp); sort(bp, bp + n, cmp); k = 0; for (i = 0; i < m; i++) { for (j = k; j < n; j++) { if (bp[j] - '0' > op[i] - '0') { k++; op[i] = bp[j]; break; } else { break; } } } for (i = 0; i < m; i++) { printf("%c", op[i]); } return 0; }
