小于 s 的最大整数
P5523. 小于 s 的最大整数
场次:2026年10月22日-AI方向 · 来源:CodeFun2000 P5523
题目描述
给定一个数组 ,和一个整数 (不存在前导 ),请你从 中选择一些整数(可以重复使用),使得组成的数字是小于 的整数,且要求尽可能的大。
输出最终构成的数字,如果不存在满足条件的整数,则输出 。
输入格式
第一行输入一个整数 (),表示数组 的元素个数。
第二行输入 个整数 ()。
第三行输入一个整数 ()。
输出格式
输出符合条件的最大整数(不能含有前导 ,例如 应该输出 ),如果不存在满足条件的整数,输出 。
单独一个 0 是合法的输出:它没有前导零,本身也是小于 的整数。
示例
示例 1
输入:
4
5 4 8 2
5416输出:
5288说明:
的前两位 、 都在 里,第三位 不在,所以四位数只能在前两位上「换小」。 的第二位是 ,把它换成比 小的最大可用数字 ,后面两位全填最大的 ,得到 ;若在第一位上换小,首位最大只能取 ,得到 ,比 小。
示例 2
输入:
3
1 2 3
111输出:
33说明:
与 等长的候选要变小,某一位上就得放比 更小的数字,而可用数字里最小的就是 ,所以三位候选一个都不存在。退到两位,每一位都填最大的 ,得到 。
解题思路
判定标准:先比长度,再比字典序
两个十进制数比较大小只有两条规则:位数多的更大;位数相同则从高位往低位数,第一个不同的位置决定大小。题目要的是「严格小于 的最大值」,于是候选只会落在两种长度上:
- 与 等长,且字典序严格更小;
- 比 短。此时不需要考虑 、……因为长度越长,能拼出的最大值越大,长度 的最大候选一定压过所有更短的候选。所以「更短」这一类只需要构造一份,就是长度 的最大值。
而且只要等长候选存在,它就一定比任何更短的数大,短候选只是「等长拼不出来时」的兜底。两类都拼不出时答案才是 。
拼数只需要三个信息,与具体用几次无关(数字可重复取用):
ds = sorted(set(digits)) # 有哪些数字可用(重复的去掉)
largest = ds[-1] # 不是首位时,每一位都填它
nonzero = [d for d in ds if d != 0] # 多位数的首位只能从这些里挑比较两个候选也不能靠 int,得在字符串上做——先比长度、再比字典序:
def bigger(a, b):
if a is None:
return b
if b is None:
return a
if len(a) != len(b):
return a if len(a) > len(b) else b
return a if a >= b else b等长候选:让与 相同的前缀尽量长
要严格小于 又不能相等,两个数一定在某个位置 上第一次分出大小,而且那个位置上候选的数字必须比 小。在它之前的每一位都必须与 一模一样——只要有一位比 大,整个数就超了;只要有一位不同,那就是「第一次分大小」的位置,与假设矛盾。
所以构造只有两种选择:
- 越靠右越好。共享前缀越长,这个候选越大:设 两个位置都可行, 的候选在第 位上仍然是 ,而 的候选在那里已经比 小了,前者必然更大。于是从右往左找第一个可行的位置。
- 在位置 上要挑「比 小的最大可用数字」;一旦换小, 右侧的每一位都填最大值
largest(右侧再大也不会让整个数超过 )。
「可行」还有两个前提,缺一个就不是合法候选: 的前 位(即 s[:i])每一位都必须是可用数字,否则前缀根本拼不出来;首位不能是 (除非整个数只有一位)。
prefix_len = 0
while prefix_len < len(s) and int(s[prefix_len]) in usable:
prefix_len += 1 # s 从头开始有多少位能被拼出来
best = None
for i in range(min(prefix_len, len(s) - 1), -1, -1):
limit = int(s[i])
smaller = [d for d in ds if d < limit and (i > 0 or d != 0 or len(s) == 1)]
if smaller: # 这一位可以变小,就是最优的切分点
best = bigger(best, s[:i] + str(smaller[-1]) + str(largest) * (len(s) - 1 - i))
break循环上界写 min(prefix_len, len(s) - 1):位置 本身必须小于 ,而且前缀长度不能超过 。等于 的长度不算「小于」,所以 最多到 (只改末位)。
短一位候选:只有一种填法
长度定为 之后,能拼出的最大数就是把每一位都填满:首位取「最大的非零数字」,其余全取 largest。没有非零数字时,这个长度上一个合法数都拼不出来,但数字 本身(长度 )仍然小于 ,所以此时答案是 "0"。 时不存在更短的长度,这一类直接跳过。
if len(s) > 1:
short_len = len(s) - 1
if nonzero:
short = str(nonzero[-1]) + str(largest) * (short_len - 1)
else:
short = "0"
best = bigger(best, short)上界 :全程字符串,一位一位地拼
题面把 的上界定到 ,也就是最多 位,这不是「注意精度」的提醒,而是一条硬约束:
- 不能把 转成整数。Python 3.11 起,
int("9"*10001)会直接抛ValueError: Exceeds the limit (4300 digits) for integer string conversion;换到定长大整数的语言里则是溢出。比较大小必须靠「位数 + 字典序」,也就是上面那个bigger。 - 不能递归地逐位构造。按位尝试天然可以写成递归,但一万层递归会撞上解释器的递归深度上限;这里写成从右往左的迭代,既没有深度问题,构造一个候选也只是 的字符串拼接。
整条路径只用到两种运算:int(s[i])(单个字符转数字,一位)和字符串拼接/比较。这就是「按字符串处理」的全部含义。
完整代码实现
import sys
def bigger(a, b):
"""在两个数(十进制字符串,无前导 0)里取更大的;None 表示这个候选不存在。"""
if a is None:
return b
if b is None:
return a
if len(a) != len(b): # 位数多的更大
return a if len(a) > len(b) else b
return a if a >= b else b # 等长就是字典序
def max_below(digits, s):
"""用 digits 里的数字(可重复使用)拼出严格小于 s 的最大整数。"""
ds = sorted(set(digits)) # 去重:同一个数字用几次都一样
usable = set(ds)
largest = ds[-1] # 不是首位时,每一位都填它最大
nonzero = [d for d in ds if d != 0] # 多位数的首位只能从这些里挑
# 候选一:与 s 等长。前缀要逐位与 s 相同,所以先看这个前缀有多长
prefix_len = 0
while prefix_len < len(s) and int(s[prefix_len]) in usable:
prefix_len += 1
best = None
# 从右往左找第一个能变小的位置:共享的前缀越长,拼出来的数越大
for i in range(min(prefix_len, len(s) - 1), -1, -1):
limit = int(s[i])
# 第 i 位换成「比 s[i] 小」的最大可用数字;首位不能是 0(除非整个数只有一位)
smaller = [d for d in ds
if d < limit and (i > 0 or d != 0 or len(s) == 1)]
if smaller:
cand = s[:i] + str(smaller[-1]) + str(largest) * (len(s) - 1 - i)
best = bigger(best, cand)
break
# 候选二:长度比 s 少一位。位数更少一定更小,取这个长度下的最大值即可
if len(s) > 1:
short_len = len(s) - 1
if nonzero:
short = str(nonzero[-1]) + str(largest) * (short_len - 1)
else:
short = "0" # 只有数字 0:能拼出的最大数就是 0
best = bigger(best, short)
return best if best is not None else "-1"
def solve():
data = sys.stdin.buffer.read().split()
if not data:
return
n = int(data[0])
digits = [int(x) for x in data[1:1 + n]]
s = data[1 + n].decode()
print(max_below(digits, s))
if __name__ == "__main__":
solve()示例推演
示例 1:,
可用数字 ,最大数字 largest = 8,最大非零数字 。
等长候选。 先数前缀: 可用, 可用, 不在集合里,所以 prefix_len = 2。从右往左试 :
- :上限 ,可用数字里没有比 小的,跳过;
- :上限 ,小于 的可用数字只有 ,取 ; 右侧两位全填 ,得到
5288,随即break。
短一位候选。 长度 :首位取最大非零数字 ,其余两位填 ,得到 888。
取大者。 bigger("5288", "888") 先比长度,,选 5288。
校验「最大」:四位数要小于 且前两位与 相同,则第三位必须小于 ,而 不在 里,这条路走不通;于是只能在前两位上换小。第二位换小取 (比 小的最大可用数字)得到 ,第一位换小取 得到 ,前者更大。三位数最多 ,五位以上必然超过 。所以 就是答案。
示例 2:,
可用数字 ,largest = 3,最大非零数字 。
等长候选。 前缀三位 、、 都在集合里,prefix_len = 3。从右往左试 :
- :上限 ,没有比 小的可用数字,跳过;
- :同上,跳过;
- :上限 ,同样没有可换的数字,跳过。
等长候选不存在:三位数若有一位比 的对应位小,那一位就得放 或更小的数字,而 不在 里;三位全取 又恰好等于 ,不满足严格小于。
短一位候选。 长度 :首位取最大非零数字 ,第二位填 ,得到 33。
取大者。 只有 33 一个候选,输出 。
顺带看一个 的情形:、。等长候选中只有 ,上限 ,没有比它小的可用数字; 又没有短候选。两类都空,输出 。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 枚举所有由 拼成、长度不超过 的数 | 每个候选都要拼接并比较,位数一多就完全跑不动 | ||
| 等长 + 短一位两类候选(最优) | 数前缀 ,每个位置最多试 个数字,候选只拼一次 |
主导项是「按位试」这一趟:,每位最多 种数字,合计约 次比较,与位数线性。空间只有两个长度 的字符串(候选与 本身),与位数的平方无关——这也是「不能转整数、不能逐位做数值运算」的另一面:一切都在字符串上进行,开销只跟长度成正比。
易错点总结
1. 从右往左扫时只比 s[i],不检查前缀拼不拼得出来
smaller = [d for d in ds if d < limit] 少写了「前缀可用」这一关,就会在一个前缀根本拼不出来的位置上换数字。、 时, 就成功了:候选拼成 2191,它确实小于 ,但里面有一个 里没有的 ;正确答案是 1999( 换首位)。这类错误不会抛异常,输出还是个「看起来合理」的数,只有回头核对「每一位都来自 」才能发现。
2. 只做等长候选,漏掉「短一位」
示例 2 就是专门用来打这一条的:、 时,等长候选一个都不存在(没有比 更小的可用数字),漏了短候选就会输出 ,而正确答案是 。同理, 且 时,正确答案也是 0 而不是 ——它属于「短一位」这一类里唯一能拼出的数。
3. 用 int(s) 比较大小
最多 位,int("9" * 10001) 在 Python 3.11+ 上直接抛 ValueError: Exceeds the limit (4300 digits) for integer string conversion,程序在第一行读取时就崩了,与贪心逻辑无关。即使绕开这个限制,把两个上万位的数转成整数再比较,也比「先比长度、再比字典序」慢得多,且换到别的语言会直接溢出。