小苯的最小好数

[题目链接](https://www.nowcoder.com/practice/9ae46830704e4d2399f025074ffcb949)

思路

给定正整数 ，求不小于 的最小"好数"，即所有数位互不相同的数。

回溯（DFS）逐位试填

从最高位到最低位，依次尝试填入数字。核心思想类似数位 DP 中的"贴上界"：

  1. 贴上界阶段：如果前面所有位都和原数一样（还没有变大），当前位只能从 对应位的数字开始往上尝试，不能更小。
  2. 松弛阶段：一旦某一位填了比原数更大的数字，后续所有位可以从 开始自由选取（只要没被用过）。
  3. 去重约束：用一个布尔数组记录 哪些数字已经使用，保证每个数字至多出现一次。

如果所有位都尝试完仍然失败（比如原数位数为 但无法构造出 位的好数），则答案一定是 位的最小好数，即 （取前 位）。这是因为好数最多有 位（数字 各用一次），所以只要位数不超过 ，一定存在解。

样例演示

输入 ：

  • 第 0 位：尝试 ，标记已用，进入下一位
  • 第 1 位：尝试 ，标记已用，进入下一位
  • 第 2 位：尝试 ，标记已用，进入下一位
  • 第 3 位：需要 ，但 已用，尝试 ，可用，填入
  • 所有位填完，结果为

复杂度分析

  • 时间复杂度：每组数据最坏 ，但由于剪枝，实际远小于此。
  • 空间复杂度：， 为数字位数，递归栈深度。

代码

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

bool dfs(string &num, int i, bool loose, vector<bool> &used) {
    if (i == (int)num.size()) return true;
    int lo = loose ? 0 : (num[i] - '0');
    char orig = num[i];
    for (int d = lo; d <= 9; d++) {
        if (!used[d]) {
            used[d] = true;
            num[i] = '0' + d;
            if (dfs(num, i + 1, loose || (d > lo), used))
                return true;
            num[i] = orig;
            used[d] = false;
        }
    }
    return false;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        char buf[20];
        scanf("%s", buf);
        string num(buf);
        vector<bool> used(10, false);
        if (dfs(num, 0, false, used)) {
            printf("%s\n", num.c_str());
        } else {
            string fail = "1023456789";
            printf("%s\n", fail.substr(0, num.size() + 1).c_str());
        }
    }
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int t = Integer.parseInt(br.readLine().trim());
        String fail = "1023456789";
        while (t-- > 0) {
            char[] num = br.readLine().trim().toCharArray();
            boolean res = dfs(num, 0, false, new boolean[10]);
            if (res) {
                sb.append(new String(num));
            } else {
                sb.append(fail.substring(0, num.length + 1));
            }
            sb.append('\n');
        }
        System.out.print(sb);
    }

    static boolean dfs(char[] num, int i, boolean loose, boolean[] used) {
        if (i == num.length) return true;
        int lo = loose ? 0 : (num[i] - '0');
        char orig = num[i];
        for (int d = lo; d <= 9; d++) {
            if (!used[d]) {
                used[d] = true;
                num[i] = (char) ('0' + d);
                if (dfs(num, i + 1, loose || d > lo, used))
                    return true;
                num[i] = orig;
                used[d] = false;
            }
        }
        return false;
    }
}