首页 > 试题广场 >

小苯的最小好数

[编程题]小苯的最小好数

热度指数：223 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\,\,\,\,\,\,\,\,\,\,$ 小苯定义一个数为好数，当且仅当这个数字的所有数位互不相同，例如： $1234$ 就是一个好数，而 $1233$ 就不是。
$\,\,\,\,\,\,\,\,\,\,$ 小苯现在有一个正整数 $x$ ，他想知道，不小于 $x$ 的最小好数是几，请你帮帮他吧。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个正整数  代表数据组数，每组测试数据描述如下：
在一行上输入一个整数  代表小苯初始拥有的数字。

输出描述:

对于每组测试数据，在一行上输出一个整数，代表不小于  的最小好数。

示例1

输入

输出

1234
9876
1

说明

算法知识视频讲解

Sen🍓🍀

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());
        String fail = "1023456789";
        while (t-- > 0) {
            char[] num = br.readLine().toCharArray();
            boolean res = dfs(num, 0, false, new boolean[10]);
            if (res) {
                sb.append(String.valueOf(num)); // 试填成功
            } else {
                sb.append(fail.substring(0, num.length + 1));
                // 失败：要多1位, 1023456..
            }
            sb.append('\n');
        }
        System.out.print(sb.toString());
    }

    // 回溯：试填, 有点数位DP的感觉
    static boolean dfs(char[] num, int i, boolean lowerLimit, boolean[] used) {
        if (i == num.length) return true; // 成功

        char origin = num[i];
        // 下界：若前面用了比原数更大的数字时 可以从0开始尝试, 否则从num[i]开始尝试
        int lower = lowerLimit ? 0 : num[i] - '0';
        for (int j = lower; j <= 9; j++) {
            if (!used[j]) {
                num[i] = (char)(j + '0');
                used[j] = true;
                if (dfs(num, i + 1, lowerLimit || j > lower, used))
                    return true; // 成功
                num[i] = origin;
                used[j] = false;
            }
        }
        return false;
    }
}

发表于 2025-10-25 21:37:34 回复(0)