UPC2022新生赛30场

问题 G: 数字替换

题目描述

味味很喜欢玩一个数字替换的游戏，数字替换游戏是这样的：给出一个 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

提示

b 中的一个 1 和 a 中的第二位上的 0 进行交换。

对于 20%的数据 1≤n，m≤10
对于 50%的数据 1≤n，m≤2000
对于 100%的数据 1≤n，m≤100000

心得：

就分享一道题目吧，这道题目我也是由于不认真读题才导致多次更改，坐题之前一定要看好条件啊，这道题目首先给出了两个条件m， n代表着输入的两个字符串的长度，但是，由于粗心吧，我直接忘记使用这两个条件了，直接当成整数输入肯定会错。

：第一遍错误代码（不想看的话可以直接蹦到最下面ac代码

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
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("%d\n", &num);
    for (i = 0; i < m; i++) {
        op[i] = getchar();
    }
    op[++i] = '\0';
    int len1 = strlen(op); //字符串的长度
    for (i = 0; op[i] != '\0'; 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 <iostream>
#include <algorithm>
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;
    /*i = 0;
    while ((op[i] = getchar()) != '\n') {
        i++;
    }
    op[i] = '\0';
    i = 0;
    while ((bp[i] = getchar()) != '\n') {
        i++;
    }
    bp[i] = '\0';*/
    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;
}