## 题目大意
给定一个正整数 x
,要求找到一个大于等于 x
的最小整数 y
,使得 y
的各位数字互不相同。我们把这种数位互不相同的数称为“好数”。
例如,输入 1233
,输出 1234
。输入 989
,输出 1023
。
## 核心思路 💡
最直接的暴力方法(逐一加一检查)容易超时。更高效的解法是构造法。我们的目标是让找到的答案 y
和 x
尽可能接近,这意味着 y
应该和 x
拥有尽可能长的相同前缀。
这个思路引导我们采用一种**“回溯修改”**的策略:
- 如果
x
本身就是好数,那它就是答案。 - 如果
x
不是好数,我们从左到右找到第一个重复的数字,这个位置就是问题的关键。 - 为了得到比
x
大的、且增幅最小的数字,我们必须修改这个重复位或它左边的某一位。显然,越靠右的修改,对数字大小的影响越小。 - 因此,我们从这个重复数字的位置开始,从右向左回溯,尝试将当前位的数字加一。并且,这个回溯过程本身还可以通过状态优化进一步提升效率,避免重复计算。
- 一旦我们成功替换了某一位的数字,这个新前缀就确定了。剩下的后缀部分,我们应该用当前还未被使用过的、最小的数字按升序依次填充。
- 如果回溯到最高位都找不到可行的替换方案,答案必然是一个位数+1的最小好数(例如
1023
)。
## 算法步骤 📝
下面是包含了状态优化的算法实现步骤:
- 检查自身:将输入数字 x 转为字符串 s。遍历 s,使用一个集合(Set)来检查是否存在重复数字。如果不存在,s 本身就是答案,程序结束。
- 定位错误点:在遍历过程中,记录下第一个重复数字的索引 first_dupe_idx。
- 回溯修改与状态优化:a. 初始化状态:在回溯开始前(即 j = first_dupe_idx 时),我们只创建一次前缀 s[0...j-1] 中使用过的数字集合 used。b. 开始回溯:然后开始一个循环,从 j 递减至 0。c. 查找替换:在每个 j,我们使用这个 used 集合来寻找一个 > s[j] 的可用替换数字 d。如果找到了,就进入下一步(构造后缀)。d. 高效更新状态:如果在当前 j 找不到可行的替换数字,我们就将 j 减一,并从 used 集合中移除s[j] 这个数字。这就完成了对 used 集合的高效更新,使其能准确反映新的、更短的前缀的状态,而无需重新扫描整个前缀来重建集合。
- 构造后缀:将 s 的前 j 位和找到的新数字 d 拼接成新的前缀 new_prefix。然后,从 0 到 9 开始遍历,依次找出还未被 new_prefix 使用过的最小数字,按顺序填充到后缀中,直到补齐 s 的原始长度。拼接好的 new_prefix 和后缀就是最终答案,打印并结束程序。
- 处理位数增加:如果回溯循环完整地执行完毕都没有找到任何可行的替换方案,则说明答案必须增加一位。此时,构造并打印出长度为 n+1 的最小好数即可(即 102...)。
## 代码实现 🏆
这是包含了状态优化的最终 Python 实现。
import sys def solve(x_str): """ 最终优化版:通过高效的状态管理进行剪枝,避免重复计算。 """ n = len(x_str) # 步骤 1: 检查输入 x_str 本身是否为好数 seen = set() first_dupe_idx = -1 for i, char in enumerate(x_str): if char in seen: first_dupe_idx = i break seen.add(char) if first_dupe_idx == -1: print(x_str) return # 步骤 2: 从第一个重复位开始,从右向左回溯 j = first_dupe_idx # 【状态优化】在这里一次性创建好 used 集合 # set(x_str[:j]) 包含了 j 前面所有位的数字 used_in_prefix = set(x_str[:j]) while j >= 0: # 步骤 3: 尝试为第 j 位找到一个更大的、且未在前缀中使用的数字 start_digit = int(x_str[j]) + 1 for d_val in range(start_digit, 10): d_char = str(d_val) if d_char not in used_in_prefix: # 找到了可行的替换,立即构建并返回最终答案 new_prefix = x_str[:j] + d_char # 步骤 4: 用干净的状态构建后缀 used_so_far = set(new_prefix) suffix_list = [] for _ in range(n - len(new_prefix)): for fill_d_val in range(10): fill_d_char = str(fill_d_val) if fill_d_char not in used_so_far: suffix_list.append(fill_d_char) used_so_far.add(fill_d_char) break print(new_prefix + "".join(suffix_list)) return # 【状态更新】如果当前位j找不到替换,则回溯到上一位 j -= 1 # 高效地更新 used 集合,只需移除 j 这一位的数字 if j >= 0: used_in_prefix.remove(x_str[j]) # 步骤 5: 如果回溯到最左边也找不到替换,说明答案需要增加一位 res = '1023456789' print(res[:n + 1]) if __name__ == "__main__": try: T_str = sys.stdin.readline() if not T_str: exit() T = int(T_str) for _ in range(T): line = sys.stdin.readline() if line: solve(line.strip()) except (IOError, ValueError, IndexError): pass