数字分列最小差
P5942. 数字分列最小差
场次:2026年10月21日-非AI方向 · 来源:CodeFun2000 P5942
题目描述
这里有一列正整数,长度记为 。列中每个数只取 到 ,并且同一个数可以反复出现。
需要把这些数拆进两个部分,每一边至少放一个数,每个数正好被用一次。两边各自占据的位置不必连在一起。同一边内部可以打乱先后,再顺着书写顺序连成一个整数。希望得到的两个整数尽量靠近。比较时只保留不小于零的差:较大的那个整数叫做 ,较小的叫做 ,二者的差记作 。
把所有能使 达到最小的整数对都列出来。每一行写一组 、、。若不同的拆法拼出了同一对整数,这一对只保留一次。多组结果里 一样小时,按 由小到大逐行给出。
输入格式
评测机经由标准输入送入全部数据。
第一行是一个整数 ,表示这一列有多长。
第二行是 个整数 ,相邻两项之间用空格隔开。
输出格式
先输出一行整数 ,表示达到最小差的整数对有多少组。
再输出 行,每一行写出三个整数 。它们满足 ,并且 ,其中 就是那个最小差。行与行之间按 由小到大排列。
数据范围
示例
示例 1
输入:
2
7 2输出:
1
7 2 5说明:
只有两个数,只能一边放一个。
较大的是 ,较小的是 ,差为 。不存在更小的差。
示例 2
输入:
3
1 9 1输出:
1
11 9 2说明:
两个 放在同一边,连成 ; 单独放在另一边。差是 。
这两个 在原列中并不相邻,中间隔着 。
若让 跟其中一个 同边,会得到 与 ,或者 与 。差分别是 和 ,都比 大。
示例 3
输入:
4
3 1 3 1输出:
2
13 13 0
31 31 0说明:
两边各拿一个 和一个 。两边都可以排成 ,也可以都排成 ,差都是 。
与 相差 ,不是最小。
一边放两个 、另一边放两个 ,得到 与 ,差是 。
最小差是 ,一共两组。按 由小到大,先写 ,再写 。
解题思路
输出的三件事:最小差、所有达到它的整数对、按 升序
读完题面,先把「要输出什么」拆成三层,这决定了代码长什么样:
- 先定最小值 ,它是所有拆法里 的最小值;
- 再收集所有达到 的 ,注意是「所有」——同一对整数换个拆法再出现一次也只算一条;
- 最后按 升序逐行输出,每行三列 , 一定不小于 。
第 2 条里的「去重」不是细枝末节:示例 1 里两个数字各自成堆,短边取 与短边取 是对称的两种枚举,同一个 会被收集两次, 直接从 变成 。
位置是自由的:真正决定结果的只有「两堆数字」
题面有三句话在反复强调同一件事:
- 「两边各自占据的位置不必连在一起」——拆的是数字的集合,不是在原序列上切一刀;
- 「同一边内部可以打乱先后」——每一边的排列是自由的;
- 「每个数正好被用一次」——两个部分是这个多重集合的一个划分。
三句话合起来,一个拆法就等价于:把 个数字分成两个非空的多重集合,然后各自随意排列。原序列里的下标完全不起作用。示例 2 的说明也是在提醒这一点:两个 在原列里隔着 ,照样能拼成 。
于是搜索空间从「按位置拆」变成「按数字组合拆」: 时,分成两堆的方式最多 种,比「排列 × 切分」小得多。
关键观察:位数差 2 位以上一定不是最优
一头一尾两个数字拼出来的整数,量级由位数决定,而位数只和两边各分到几个数字有关。这给出一个可以严格证明的剪枝。
先看平衡拆法最坏能差到什么程度。设 ,两边都是 位:
设 ,一边 位、一边 位( 自然是位数多的那边):
再看位数相差 位以上(也就是短边只有 位或更少)的拆法能有多好:
- :长边至少 位,,,于是 ;
- :长边至少 位,,,于是 。
两种情况里,不平衡拆法的下界都比平衡拆法的上界还大 2,所以最小值只可能出现在位数最接近的拆法上:短边恰有 位。
这条结论把枚举量压得很小:只需要决定「哪 个数字去短边」。 时最多 种组合,去重之后更少。
short = k // 2 # 短边(Q 所在边)的数字个数
combos, seen = [], set()
def pick(start, left, chosen):
if left == 0:
key = tuple(sorted(chosen)) # 只看数字多重集合,不看下标
if key not in seen:
seen.add(key)
combos.append(key)
return
for i in range(start, k):
chosen.append(digits[i])
pick(i + 1, left - 1, chosen)
chosen.pop()
pick(0, short, [])seen 里存的是排序后的数字元组,所以 [1,9,1] 里两个 换来换去只算同一种组合,重复的枚举被挡在入口处。
每一边能拼出哪些整数
给定一堆数字,能拼出的整数就是它的全部不同排列:长度为 时最多 个,(平衡拆法的一边最多 位, 时另一边的短边是 位)时最多 个。数字都是 ,不用担心前导零。
去重的办法是「相同数字只取第一个」:把剩余数字排好序,递归时跳过与前一个相同的分支,同一层就不会用同一个数字试两遍。
def all_numbers(ds):
out = set()
def dfs(rem, cur):
if not rem:
out.add(cur)
return
for i, d in enumerate(rem):
if i and rem[i - 1] == d: # 相同数字只取第一个,避免重复排列
continue
dfs(rem[:i] + rem[i + 1:], cur * 10 + d)
dfs(tuple(sorted(ds)), 0)
return sorted(out)返回升序列表是为了下一步能直接双指针。
求最小差:两组升序值双指针
固定一种数字组合之后,两边能拼出的整数集合就各自确定了,两边独立取值,所以「这一组合里的最小差」就是「两个升序表里最近的一对数」。
best = None
for va, vb in groups:
j = 0
for x in va: # va 升序
while j + 1 < len(vb) and vb[j] < x:
j += 1 # j 停在「最后一个小于 x」的位置
for t in (j - 1, j, j + 1): # 左右各看一格就够
if 0 <= t < len(vb):
d = abs(x - vb[t])
if best is None or d < best:
best = dj 只往前走不回退,所以一个组合内是 。看 j-1, j, j+1 三格的原因是 j 停在「小于 的最后一个」,与 最接近的值只可能在它和它右边那一格。
收集所有达到最小差的整数对
已知 之后,收集就退化成「找等值对」:对每个 ,另一张表里落在 区间的值都可能是答案,用二分定位区间左端,再顺着区间扫完。
pairs = set()
for va, vb in groups:
for x in va:
lo = bisect_left(vb, x - best)
while lo < len(vb) and vb[lo] <= x + best:
if abs(x - vb[lo]) == best:
pairs.add((max(x, vb[lo]), min(x, vb[lo]))) # 统一成 P >= Q
lo += 1
out = [str(len(pairs))]
for p, q in sorted(pairs): # 按 P 升序
out.append(f"{p} {q} {p - q}")三个细节都在这一小段里:
max/min把「谁当 」统一掉,同一个整数对的两个方向自然合成一条;pairs用set,不同数字组合拼出的同一对整数也只留一条(题面要求「这一对只保留一次」);- 最后按元组排序,第一关键字是 ,正好是题面要求的顺序。
完整代码实现
import sys
from bisect import bisect_left
def all_numbers(ds):
"""数字多重集合 ds 能拼出的全部整数(去重、升序)。数字都是 1~9,无前导零问题。"""
out = set()
def dfs(rem, cur):
if not rem:
out.add(cur)
return
for i, d in enumerate(rem):
if i and rem[i - 1] == d: # 相同数字只取第一个,避免重复排列
continue
dfs(rem[:i] + rem[i + 1:], cur * 10 + d)
dfs(tuple(sorted(ds)), 0)
return sorted(out)
def solve():
data = sys.stdin.buffer.read().split()
if not data:
return
k = int(data[0])
digits = [int(x) for x in data[1:1 + k]]
short = k // 2 # 短边(Q 所在边)的数字个数
# 枚举短边的数字组合:结果只取决于左右两边的数字多重集合
combos, seen = [], set()
def pick(start, left, chosen):
if left == 0:
key = tuple(sorted(chosen))
if key not in seen:
seen.add(key)
combos.append(key)
return
for i in range(start, k):
chosen.append(digits[i])
pick(i + 1, left - 1, chosen)
chosen.pop()
pick(0, short, [])
groups = []
for key in combos:
rest = list(digits)
for d in key:
rest.remove(d) # 补集:长边分到的数字
groups.append((all_numbers(key), all_numbers(rest)))
# 第一遍:双指针求最小差
best = None
for va, vb in groups:
j = 0
for x in va:
while j + 1 < len(vb) and vb[j] < x:
j += 1
for t in (j - 1, j, j + 1):
if 0 <= t < len(vb):
d = abs(x - vb[t])
if best is None or d < best:
best = d
# 第二遍:只收差恰为 best 的整数对
pairs = set()
for va, vb in groups:
for x in va:
lo = bisect_left(vb, x - best)
while lo < len(vb) and vb[lo] <= x + best:
if abs(x - vb[lo]) == best:
pairs.add((max(x, vb[lo]), min(x, vb[lo])))
lo += 1
out = [str(len(pairs))]
for p, q in sorted(pairs):
out.append(f"{p} {q} {p - q}")
sys.stdout.write("\n".join(out) + "\n")
if __name__ == "__main__":
solve()示例推演
示例 1: 只有一种拆法
数字是 , 所以 short = 1,短边只能分到一个数字,组合有两种:(2) 与 (7)。补集分别是 (7) 与 (2),于是 groups 里是两组对称的枚举:
| 短边 | 补集 | 短边能拼出的整数 | 补集能拼出的整数 |
|---|---|---|---|
双指针在两组里都得到 ,所以 。收集阶段把两种方向都归一成 ,set 只留一条:
1
7 2 5与题面一致。
示例 2: 为什么只能是「两个数 vs 一个数」
时 short = 1,也就是短边一定只有 位,符合上面对位数的分析(,平衡拆法是 位与 位)。数字 的短边组合去重后只有两种:(1) 与 (9)。
| 短边 | 补集 | 短边值 | 补集值 | 最小差 |
|---|---|---|---|---|
全局最小差 ,达到它的只有 ,输出 1 与 11 9 2。
注意第一种组合里 与 是同一堆数字的两种排列:把 放在十位还是个位,差就从 变成 。这就是「每一边都要枚举全部排列」的原因——只取字典序最小的那一种排列会漏掉更优的排法。
示例 3:为什么必须把两种排列都当候选,又必须去重
数字是 , 时 short = 2,两边都是 位。按数字组合去重后有三种拆法:
| 短边 | 补集 | 短边值 | 补集值 | 最小差 |
|---|---|---|---|---|
第三种其实是第一种的对称写(两边互换),因为 与谁叫短边无关,所以它算出的最小差同样是 ,不影响结果。
真正的答案来自第二种:两边都是 ,都排成 得到 ,都排成 得到 ,差都是 。收集时 max/min 还会把 与 这种对称方向合成同一条,所以 pairs 里只有两组,按 升序输出:
2
13 13 0
31 31 0若这里不把 与 两种排列都算进候选,就只能得到 , 会错成 。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 枚举所有「排列 + 切分」再逐对比差 | 时约 对,Python 跑不动 | ||
| 只枚举平衡拆法 + 每边全排列 + 双指针求最小差(最优) | ,每边至多 个值,实测 也在毫秒级 |
第一行是「想到的第一种做法」:把原序列全排列,再在每个位置切一刀,两边直接拼。它的正确性没问题(任何拆法都能写成「某个全排列的某个前缀 + 后缀」),但 时有 个候选对,量级是 ,纯 Python 会超时。
第二行就是上面的做法:位数分析先把候选压到 种数字组合,每种组合两边各至多 个值,求最小差走双指针 ,最后收集时二分定位区间、只扫落在 附近的值。空间只存每边至多 个整数。
易错点总结
1. 把「拆」理解成在原序列上切一刀
写成 for i in range(1, k): A, B = digits[:i], digits[i:] 之后,位置被当成了约束。示例 2 的 只允许 与 两种切法,得到的最小差是 ( 与 )而不是题面的 —— 因为题面允许两个 跨过中间的 拼成 。这一行改错,示例 2、示例 3 都会错,而示例 1()恰好两种理解一致,只看第一组样例发现不了。
2. 每一边只试一种排列
all_numbers 只返回「把数字升序接起来」的那一个值时,每堆数字只有一种排法。示例 3 就会退化成: 只能拼 ,两边都是 ,最小差还是 ,但 这一组永远找不出来, 输出 而正确是 。反过来,示例 2 里 与 的差分别是 与 ,只试升序排列同样会把「更差的排法」当成唯一结果。
3. 收集结果用列表,同一对整数被写两次
pairs 写成 pairs = [] 再 append,同一个整数对会在「短边取这一堆」与「短边取它的补集」两次对称枚举里各出现一次——示例 1 的短边取 与取 都会得到 ,于是输出变成 2 加两行一模一样的 7 2 5。若再把拆法改成按位置 mask 枚举、不做多重集合去重,重复还会更多:示例 3 的 对应 个 mask, 会变成 。pick 里的 seen 与 pairs = set() 两道防线缺一不可。