找到通过插入给定数字形成的最小数字

问题描述

给定两个数字n和m，以及数字d。现在希望在n的十进制表示中插入若干个数字d，使得插入后的数字比m大，并且插入的数字最小。如果无法插入，则输出不可能。

问题分析

1. 简化问题

首先，我们可以将n和m进行分解，将问题简化为在一个长度为l的数字s中插入若干个数字d，使得插入后的数字大于数字m，并且插入的数字最小。其中，l是数字s的长度。

显然，若要插入若干个数字d使得插入后的数字最小，需要尽可能让高位的数字d尽量小，因为高位上的数字对数字大小的贡献最大。

2. 解法思路

接下来，我们来考虑如何在数字s中插入数字d，使得插入后的数字最小：

我们首先从高位向低位遍历数字s中的每一个数字。假设当前遍历到的数字为x，我们需要将数字d插入到这个数字的后面。

如果x大于等于d，则直接在x后面插入d即可。

如果x小于d，则需要删除数字x，然后在x所在的位置上插入数字d。由于删除x后，后面的数字都会向前移动一位，我们需要在这些数字中寻找一个最小的数字y，使得y大于等于d。如果存在这样的数字y，则在x的位置上插入数字y即可。否则，我们需要继续往前遍历下一个数字。

当遍历到头仍然无法找到数字y时，即表示无法在数字s中插入数字d，使得插入后的数字大于m并且插入的数字最小。

3. 代码实现

#include <iostream>

#include <algorithm>
#include <cstring>
using namespace std;
const int N = 20, INF = 0x3f3f3f3f;
int n, m, d;
int s[N], ns[N];
// 判断能否在数字s的某个位置上插入数字d，使得插入后的数字大于等于m
bool check(int p)
{
    // 将数字d插入到s的第p+1位后
    int len = 0;
    for (int i = 0; i <= p; i ++ ) ns[len ++ ] = s[i];
    ns[len ++ ] = d;
    for (int i = p + 1; i < n && len <= n; i ++ ) ns[len ++ ] = s[i];
    // 比较插入后的数字和m的大小
    for (int i = 0; i < n; i ++ )
        if (ns[i] > m) return true;
        else if (ns[i] < m) return false;
    return true;
}
int main()
{
    scanf("%d%d%d", &n, &m, &d);
    for (int i = 0; i < n; i ++ ) scanf("%d", &s[i]);
    bool flag = false;
    for (int i = 0; i < n; i ++ )
        if (s[i] < d && check(i))
        {
            int len = 0;
            for (int j = 0; j <= i; j ++ ) ns[len ++ ] = s[j];
            for (int j = i + 1; j < n && len <= n; j ++ )
            {
                int t = INF;
                for (int k = d; k <= 9; k ++ )
                    if (check(j - 1))
                    {
                        t = k;
                        break;
                    }
                ns[len ++ ] = t;
                d = min(d, t);
            }
            flag = true;
            break;
        }
    if (!flag) puts("impossible");
    else
        for (int i = 0; i < n; i ++ )
            printf("%d ", ns[i]);
    return 0;
}