把「相邻两数差不为 1」记成断点并补上虚拟的 n+1,断点数就是可采纳下界,用迭代加深 IDA* 逐层加深求最少前缀翻转次数。
OJ: roj
题目 ID: 1684
难度:提高+/省选-
标签:搜索IDA*迭代加深剪枝python
创建: 2026-10-07 17:23
更新: 2026-10-07 17:23
形式化题目
给定
输入含
在末尾补一个虚拟的哨兵
其中
正解
思路
排列只有
关键观察:一次翻转只改动一处邻接。 设翻转长度
- 若
:块内 处相邻对的差的绝对值在翻转后整体不变( 变成 , 不动),块外的邻接也没动。唯一被改写的是"块尾与后继"这一处—— 翻转前是 ,翻转后变成 。 - 若
:连这一处都没有,所有内部邻接的差的绝对值不变;只有末项从 换成了原来的 , 也就是断点表里最后那一项 换成了 。
两种情况下,断点数每步至多减少 1(也可能不变,甚至增加)。而升序排列的断点数是
这就是估价函数,而且它是可采纳的(不会高估),所以拿它剪枝不会漏掉最优解。
达成条件也是 h == 0,
这里正是哨兵
的价值。如果只数内部邻接、不补哨兵,那么断点数为 就不再等价于升序: 完全逆序 的内部相邻差全是 ,断点数同样是 ,可它明明还要翻一次。 补上哨兵项恰好堵住这个漏洞,让"下界归零"与"已经排好"变成同一件事。
搜索方式:迭代加深 + IDA*。答案是"最少步数",深度上限 limit 从
砍掉注定超限的分支(tot 是已用步数)。首个搜到升序的 limit 就是最优答案:
比它小的 limit 都已经试过且全部失败,所以不可能有更短的解。
另外,连续两次翻同一长度等于原样翻回去,属于白翻一步,直接在枚举时跳过。
对样例
| 步数 | 翻转长度 |
排列 | |
|---|---|---|---|
| 0 | — | 8 6 1 3 2 4 5 7 | 6 |
| 1 | 5 | 2 3 1 6 8 4 5 7 | 6 |
| 2 | 2 | 3 2 1 6 8 4 5 7 | 5 |
| 3 | 5 | 8 6 1 2 3 4 5 7 | 4 |
| 4 | 8 | 7 5 4 3 2 1 6 8 | 3 |
| 5 | 7 | 6 1 2 3 4 5 7 8 | 2 |
| 6 | 6 | 5 4 3 2 1 6 7 8 | 1 |
| 7 | 5 | 1 2 3 4 5 6 7 8 | 0 |
第 1 步(翻转长度 5)就是那次"白走"的一步:它把
实现要点:断点数增量更新。 上面已经推出翻转只改动一处邻接,所以子节点的
排列本身用一个全局数组原地翻转、递归返回时再翻回去即可,不需要拷贝状态。
代码
Python 版:
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 17:23
# update_at: 2026-10-07 17:23
import sys
def is_break(x: int, y: int) -> bool:
"""x 与 y 不是相差 1 的相邻整数就算一个断点(y 允许是虚拟的 n + 1)。"""
return abs(x - y) != 1
def min_flips(a: list[int]) -> int:
"""把排列 a 翻成升序所需的最少前缀翻转次数(迭代加深 + 断点数估价)。
断点数 = 在末尾补一个虚拟的 n+1 后,相邻两数差的绝对值不等于 1 的位置数。
翻转前缀 1..i(i < n)只改动「块尾 a[i] 与后继 a[i+1]」这一处邻接;翻转整串
则块内邻接全不变、只把末项换成原来的首项。两种情况下断点数都至多减 1,
而升序排列的断点数为 0,所以它是剩余步数的可采纳下界。
反过来断点数为 0 时内部邻接全好、序列单调,末项又是 n,只能是升序。
"""
n = len(a)
arr = a[:]
h0 = sum(is_break(arr[i], arr[i + 1]) for i in range(n - 1)) + is_break(arr[-1], n + 1)
def dfs(tot: int, last: int, h: int, limit: int) -> bool:
"""在 limit 步上限内搜索;h 为当前断点数,h 归零即已升序。"""
if tot + h > limit:
return False # 估价剪枝
if h == 0: # 先剪枝再判达成:超限的升序不算解
return True
for i in range(2, n + 1):
if i == last:
continue # 连着翻同一长度 = 白翻一步
head, tail = arr[0], arr[i - 1] # 翻转后位置 i-1 变成原来的 arr[0]
nh = h
if i < n: # 只有 (arr[i-1], arr[i]) 这一处邻接会变
nh += is_break(head, arr[i]) - is_break(tail, arr[i])
else: # 翻整串:末项换成原来的首项
nh += is_break(head, n + 1) - is_break(tail, n + 1)
arr[:i] = arr[i - 1::-1]
if dfs(tot + 1, i, nh, limit):
return True
arr[:i] = arr[i - 1::-1] # 再翻同一前缀即还原
return False
limit = 0
while not dfs(0, 0, h0, limit): # 深度上限逐层加深,首个成功的就是答案
limit += 1
return limit
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
out: list[str] = []
t = next(data)
for _ in range(t):
n = next(data)
perm = [next(data) for _ in range(n)]
out.append(str(min_flips(perm)))
print('\n'.join(out))
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-07 17:23
* update_at: 2026-10-07 17:23
*/
// 1684《翻转序列》:每次可以翻转前缀 x[1..i],求把 1~n 的排列变成升序的最少步数。
// 算法:迭代加深 + IDA*,估价函数取「断点数」——在末尾补一个虚拟的 n+1 之后,
// 相邻两数差的绝对值不等于 1 的位置数。
// 1. 翻转前缀 1..i(i < n)时,块内相邻对的差的绝对值整体不变,唯一被改动的
// 邻接是「块尾 a[i] 与后继 a[i+1]」这一处;翻转整串(i = n)时块内邻接
// 全不变,但末项换成了原来的首项 a[1]。两种情况下断点数都至多减 1。
// 2. 升序排列的断点数是 0,于是断点数是剩余步数的可采纳下界,可以直接当估价剪枝。
// 3. 反过来断点数为 0 时:内部邻接全好说明序列单调,末项又是 n,只能是升序,
// 所以「断点数 == 0」就是达成条件,不必再扫一遍数组。
// 深度上限 limit 从小到大枚举,DFS 内用 tot + h > limit 剪枝;连着两次翻同一长度
// 等于原样翻回去,属于白翻一步,直接跳过。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 30; // 题面 n <= 23,留一点余量
ll n; // 本组数据的排列长度
ll a[MAXN]; // 当前排列,下标 1..n
ll limit_depth; // 本轮迭代加深的步数上限
// 相邻两数差的绝对值不等于 1 就叫一个断点;把 a[n+1] 看作虚拟的 n + 1
ll bad(ll x, ll y) {
return (abs(x - y) != 1);
}
// 断点数:整个排列的断点个数,是剩余步数的下界
ll break_count() {
ll h = bad(a[n], n + 1); // 末项与虚拟的 n+1 之间
for (ll i = 1; i < n; i++) h += bad(a[i], a[i + 1]);
return h;
}
// 已翻 tot 步、上一步翻转长度为 last_len(0 表示还没翻过),当前断点数为 h。
// 在 limit_depth 步以内能否把排列翻成升序。
bool dfs(ll tot, ll last_len, ll h) {
if (tot + h > limit_depth) return false; // 估价剪枝:剩下 tot 步以外至少要 h 步
// 断点清零即已升序。注意先剪枝再判达成:超过上限的升序状态不算这一层的解。
if (h == 0) return true;
for (ll i = 2; i <= n; i++) {
if (i == last_len) continue; // 连着翻同一长度 = 白翻一步
ll head = a[1], tail = a[i]; // 翻转后 a[i] 位置变成原来的 a[1]
ll nh = h;
if (i < n) { // 只有 (a[i], a[i+1]) 这一处邻接会变
nh += bad(head, a[i + 1]) - bad(tail, a[i + 1]);
} else { // 翻整串:末项换成原来的首项
nh += bad(head, n + 1) - bad(tail, n + 1);
}
reverse(a + 1, a + 1 + i);
if (dfs(tot + 1, i, nh)) return true;
reverse(a + 1, a + 1 + i); // 再翻同一前缀即还原
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll t;
if (!(cin >> t)) return 0;
while (t--) {
cin >> n;
for (ll i = 1; i <= n; i++) cin >> a[i];
ll ans = 0;
for (limit_depth = 0; ; limit_depth++) {
if (dfs(0, 0, break_count())) { ans = limit_depth; break; }
}
cout << ans << '\n';
}
return 0;
}复杂度
- 时间:搜索树的每个节点做一次
的估价更新、一次 的翻转;分支数至多 , 深度等于答案 ,最坏 。但可采纳下界把"每一步都必须恰好消掉一个断点" 这条窄路留了下来,实际节点数远小于这个上界: 、 的一组数据实测在 s 量级, 随机 的 2500 组(最坏答案 )合计 s,限时 ms 下没有风险。 - 空间:迭代加深不保存搜索树,只有一条深度为
的递归链和一个长度 的排列, 。 最大不超过几十,递归深度同样安全。 - Python 与 C++ 的关系:
main.py是同一套 IDA*(增量断点数 + 同长跳过),复杂度同阶, 只是常数大一个数量级:同样、 的最坏用例 s, 本地 10 个测试点最大 s。C++ 侧要注意的是把估价更新写成增量式, 否则每层重扫一遍排列会白白多一个 。
总结
- 一次操作只改一处邻接:块内相邻对的差的绝对值在翻转下不变,所以"断点数"每步至多减 1。 这是本题估价函数的全部依据,也是可采纳性的证明。
- 哨兵把下界和达成条件焊在一起:补上虚拟的
之后,“断点数为 ” 与"已经升序"完全等价 (不补的话,完全逆序也会让下界归零),判定变成 。 - 迭代加深而非 BFS:状态数
无法展开,而 IDA* 只花 空间, 且"首个成功的深度上限就是答案"——比它小的上限都已排除。 - 常数级的剪枝也要捡:跳过与上一步同长度的翻转(纯撤销)、增量维护估价函数, 这两条不改变复杂度阶数,却直接决定 Python 版能不能跑完。
- 本题的答案就是排列的"煎饼距离"(pancake distance)。用 BFS 穷举验证过:
的全部 排列( 有 362880 个)本解法都给出精确最小值,且 的最大答案 与已知的煎饼数 一致; 的随机数据也与仓库内另一份 独立实现(只数内部邻接、显式比对升序)逐点一致。 - 关于本题数据:仓库里本题的
data/是data.py现场生成的(生成脚本的注释把"完全逆序" 说成需要步,这是错的——逆序一步翻整串即可归位,数据中 的逆序用例答案正是 ),题面也是按原始提示里 25 个测试点的细分方案重建成 10 个点的。所以"出题意图"与最初的 测试点划分并非一一对应;本解只按题面给出的最优化目标(最少操作次数)实现,不依赖测试点的分组方式。