题目思路

思路：贪心

插入一个数字后，其代替原有位置的数，要使得新的数的值越大。

原数 $a$ 的长度为 $n$ ，数的索引从 $1$ 开始，假设插入的位置为 $k$，即插入后，组成为：$[1, k] + number + [k, n]$

数 $number$ 有两种插入的位置：

• 一种是在 $[1, n]$ 这些位置之前
• 一种是在最后一个位置 $n$ 之后

考虑如何选择这两种位置：

• 如果 $number$ 不比 $s[1, n]$ 中的任意一个数大，那么其放在最后即可。

• 如果 $number$ 比 $s[1, n]$ 中至少一个数大，那么就可以放在这些数前面，如何选择？

  找到 $s[i] < number$ 的最小的 $i$ ，将 $number$ 插在 $s[i]$ 前面。这么选择是因为越靠前的位权值越大，如 $12345$ 中 $1$ 是万位，$2$ 是千位，$3$ 是百位，$2$ 是十位，$1$ 是个位，所以 $number$ 插入在 $s[i]$ 前面，这个 $i$ 越小，插入后 $number$ 给整个新的数增加的值就越大。

时间复杂度：$O(n)$

类似题目推荐

LeetCode

1. 402. 移掉 K 位数字

Codefun2000

美团还是挺喜欢考贪心的，但是大部分是简单贪心吧，如下所示

1. P1137 美团 2023.04.01-第一题-整理
2. P1077 美团 2023.3.11-第一题-字符串修改
3. P1024 百度 2022.9.13-01反转
4. P1235. 美团 2023.04.15-实习-第一题-字符串前缀
5. P1089 美团 2023.3.18.10点-第三题-塔子哥的回文串

代码

C++

#include <bits/stdc++.h>
using namespace std;

void solve() {
    string a;
    int b;

    cin >> a >> b;

    for (int i = 0; i < a.size(); ++i) {
        // 从小到大枚举，一旦找到一个小于 b 的数字，就将 b 插入在其之前
        if (a[i] < (b + '0')) {
            cout << a.substr(0, i) + to_string(b) + a.substr(i) << "\n";
            return ;
        }
    }

    // 如果 b 小于 a 中所有数字，就将 b 插入到所有数之后即可。
    cout << a + to_string(b) << "\n";
}

int main()
{
    int T;
    cin >> T;
    while (T--) solve();

    return 0;
}

python

def solve():
    a, b = input().split()
    for i in range(len(a)):
        # 从小到大枚举，一旦找到一个小于 b 的数字，就将 b 插入在其之前
        if a[i] < str(b):
            print(a[:i] + str(b) + a[i:])
            return

    # 如果 b 小于 a 中所有数字，就将 b 插入到所有数之后即可。
    print(a + str(b))


T = int(input())
for _ in range(T):
    solve()

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int T = scanner.nextInt();
        while (T-- > 0) {
            String a = scanner.next();
            int b = scanner.nextInt();

            for (int i = 0; i < a.length(); i++) {
                // 从小到大枚举，一旦找到一个小于 b 的数字，就将 b 插入在其之前
                if (a.charAt(i) < (b + '0')) {
                    System.out.println(a.substring(0, i) + b + a.substring(i));
                    break;
                }

                // 如果 b 小于 a 中所有数字，就将 b 插入到所有数之后即可。
                if (i == a.length() - 1) {
                    System.out.println(a + b);
                }
            }
        }
    }
}

Go

package main

import (
    "fmt"
    "strconv"
)

func solve() {
    var a string
    var b int

    fmt.Scan(&a, &b)

    for i := 0; i < len(a); i++ {
        // 从小到大枚举，一旦找到一个小于 b 的数字，就将 b 插入在其之前
        if a[i] < byte(b+'0') {
            fmt.Println(a[:i] + strconv.Itoa(b) + a[i:])
            return
        }
    }

    // 如果 b 小于 a 中所有数字，就将 b 插入到所有数之后即可。
    fmt.Println(a + strconv.Itoa(b))
}

func main() {
    var T int
    fmt.Scan(&T)
    for T > 0 {
        solve()
        T--
    }
}

Js

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {
    input += data;
    return;
});
process.stdin.on('end', () => {
    const lines = input.trim().split('\n');
    let T = parseInt(lines[0]);

    for (let i = 1; i <= T; i++) {
        let [a, b] = lines[i].trim().split(" ");

        for (let j = 0; j < a.length; j++) {
            // 从小到大枚举，一旦找到一个小于 b 的数字，就将 b 插入在其之前
            if (a[j] < b) {
                console.log(a.substring(0, j) + b + a.substring(j));
                break;
            }

            // 如果 b 小于 a 中所有数字，就将 b 插入到所有数之后即可。
            if (j === a.length - 1) {
                console.log(a + b);
            }
        }
    }
});

题目描述

小美是一个数学爱好者，他经常思考各种数字之间的奥秘。今天，他想要解决一个有趣的问题：如何在一个数字中插入一个数字，以得到最大的结果？

他发现这个问题很有挑战性，因为他必须找到一种方法，能够在给定的数字中插入一个数字，使得插入后的结果最大。于是，他开始思考并设计了一种算法来解决这个问题。

算法的核心思想是：首先将第一个数字转化为字符串，然后将第二个数字插入到字符串的不同位置，得到多个可能的结果。最后，从中选择最大的一个数字作为最终的结果。

小美已经写好了这个算法，并请你帮忙测试一下。请编写一个程序，输入小美手上的两个数字，输出插入后得到的最大数字。(前导零正常输出)

输入描述

输入第一行为一个数字$T$，表示有$T$组测试样例

接下来的$T$行对于每一组数据，包含一行有 $2$个空格隔开的整数，表示任意正整数 $a$ 和待插入的数字 $b$，

$1$ $\leq$ $T$ $\leq$ $10$, 1 $\leq$ $a$ $\leq$ $10 ^{50000}$ , $0$ $\leq$ $b$ $\leq$ $9$

输出描述

对于每组数据，输出一行，包括一个整数，得到最大的整数。

样例

输入

5
123456 8
58264 2
44 5
10086 0
8 0

输出

8123456
582642
544
100860
80