翻转序列

GitHub跳转原题关系图返回列表

把「相邻两数差不为 1」记成断点并补上虚拟的 n+1,断点数就是可采纳下界,用迭代加深 IDA* 逐层加深求最少前缀翻转次数。

OJ: roj

题目 ID: 1684

难度:提高+/省选-

标签:搜索IDA*迭代加深剪枝python

创建: 2026-10-07 17:23

更新: 2026-10-07 17:23

形式化题目

给定 1∼n1 \sim n 的一个排列 xx。一次操作选定一个长度 i∈[2,n]i \in [2, n],把前缀 x1∼xix_1 \sim x_i 整体翻转 (其余元素不动)。求把 xx 变成升序排列 (1,2,…,n)(1, 2, \dots, n) 所需的最少操作次数。

输入含 tt 组数据(t=5t = 5),每组给出 nn 与排列 xx,每组输出一行一个整数表示答案; n⩽23n \leqslant 23。

在末尾补一个虚拟的哨兵 xn+1=n+1x_{n+1} = n + 1,定义排列的断点数

h(x)  =  ∑i=1n[ ∣xi−xi+1∣≠1 ],xn+1=n+1, h(x) \;=\; \sum_{i=1}^{n} \bigl[\,|x_i - x_{i+1}| \neq 1\,\bigr], \qquad x_{n+1} = n+1,

其中 [⋅][\cdot] 是示性函数:相邻两个数(末项与哨兵也算相邻)不是"相差 1 的相邻整数"就记一个断点。 目标状态 id=(1,2,…,n)\mathrm{id} = (1, 2, \dots, n) 的断点数恰好是 00。

正解

思路

排列只有 23!23! 种,状态空间大到无法直接 BFS;而"翻转前缀"这个操作又天然适合深搜 + 估价剪枝, 因为一次翻转对排列的"混乱程度"只影响一个局部。先把这句话变精确。

关键观察:一次翻转只改动一处邻接。 设翻转长度 ii。

  • 若 i<ni < n:块内 i−1i-1 处相邻对的差的绝对值在翻转后整体不变((a,b)(a, b) 变成 (b,a)(b, a), ∣a−b∣|a-b| 不动),块外的邻接也没动。唯一被改写的是"块尾与后继"这一处—— 翻转前是 (xi,xi+1)(x_i, x_{i+1}),翻转后变成 (x1,xi+1)(x_1, x_{i+1})。
  • 若 i=ni = n:连这一处都没有,所有内部邻接的差的绝对值不变;只有末项从 xnx_n 换成了原来的 x1x_1, 也就是断点表里最后那一项 [ ∣xn−(n+1)∣≠1 ]=[xn≠n][\,|x_n - (n+1)| \neq 1\,] = [x_n \neq n] 换成了 [x1≠n][x_1 \neq n]。

两种情况下,断点数每步至多减少 1(也可能不变,甚至增加)。而升序排列的断点数是 00, 于是从当前状态走到升序至少还要 hh 步:

剩余步数  ⩾  h(x). \text{剩余步数} \;\geqslant\; h(x).

这就是估价函数,而且它是可采纳的(不会高估),所以拿它剪枝不会漏掉最优解。

达成条件也是 h=0h = 0。 反过来看:断点数清零意味着每个内部邻接的差都是 ±1\pm 1。 值域是 1∼n1 \sim n 且每个数恰好出现一次,沿"±1\pm 1 步"走一遍且不重复只能是单调的; 再加上末项那一项 [xn≠n]=0[x_n \neq n] = 0 给出 xn=nx_n = n,单调就只能是递增,即已经升序。 所以判定"是否已达成"就是判定 h == 0,O(1)O(1) 即可,不必再扫一遍数组比对。

这里正是哨兵 n+1n+1 的价值。如果只数内部邻接、不补哨兵,那么断点数为 00 就不再等价于升序: 完全逆序 n,n−1,…,1n, n-1, \dots, 1 的内部相邻差全是 11,断点数同样是 00,可它明明还要翻一次。 补上哨兵项恰好堵住这个漏洞,让"下界归零"与"已经排好"变成同一件事。

搜索方式:迭代加深 + IDA*。答案是"最少步数",深度上限 limit 从 00 开始逐层加一, 在深度上限内做 DFS,用

tot+h  >  limit  ⟹  剪枝 \mathrm{tot} + h \;>\; \mathrm{limit} \;\Longrightarrow\; \text{剪枝}

砍掉注定超限的分支(tot 是已用步数)。首个搜到升序的 limit 就是最优答案: 比它小的 limit 都已经试过且全部失败,所以不可能有更短的解。 另外,连续两次翻同一长度等于原样翻回去,属于白翻一步,直接在枚举时跳过。

对样例 x=(8,6,1,3,2,4,5,7)x = (8, 6, 1, 3, 2, 4, 5, 7),补哨兵 99 后有六个断点(8 ⁣− ⁣68\!-\!6、6 ⁣− ⁣16\!-\!1、1 ⁣− ⁣31\!-\!3、 2 ⁣− ⁣42\!-\!4、5 ⁣− ⁣75\!-\!7、7 ⁣− ⁣97\!-\!9;3 ⁣− ⁣23\!-\!2 与 4 ⁣− ⁣54\!-\!5 是相连的),故答案至少是 66,实际为 77—— 中间必然有一步没能减少断点:

步数 翻转长度 ii 排列 hh
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)就是那次"白走"的一步:它把 22 提到最前面凑成 2 32\,3, 断点数原地不动,但为第 2 步一次消掉一个断点铺好了路。这也说明下界 hh 只能当剪枝用, 不能直接当答案输出。

实现要点:断点数增量更新。 上面已经推出翻转只改动一处邻接,所以子节点的 hh 可以由父节点 O(1)O(1) 算出,不必每次重扫整个排列:

h子=h父+[ ∣x1−xi+1∣≠1 ]−[ ∣xi−xi+1∣≠1 ](i<n), h_{\text{子}} = h_{\text{父}} + [\,|x_1 - x_{i+1}| \neq 1\,] - [\,|x_i - x_{i+1}| \neq 1\,] \quad (i < n),
h子=h父+[x1≠n]−[xn≠n](i=n). h_{\text{子}} = h_{\text{父}} + [x_1 \neq n] - [x_n \neq n] \quad (i = n).

排列本身用一个全局数组原地翻转、递归返回时再翻回去即可,不需要拷贝状态。

代码

Python 版:

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++ 版(同一算法):

cpp
/**
 * 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;
}

复杂度

  • 时间:搜索树的每个节点做一次 O(1)O(1) 的估价更新、一次 O(i)O(i) 的翻转;分支数至多 n−1n-1, 深度等于答案 dd,最坏 O((n−1)d)O\bigl((n-1)^d\bigr)。但可采纳下界把"每一步都必须恰好消掉一个断点" 这条窄路留了下来,实际节点数远小于这个上界:t=5t = 5、n=23n = 23 的一组数据实测在 0.010.01 s 量级, 随机 n=23n = 23 的 2500 组(最坏答案 2424)合计 0.630.63 s,限时 10001000 ms 下没有风险。
  • 空间:迭代加深不保存搜索树,只有一条深度为 dd 的递归链和一个长度 nn 的排列, O(n)O(n)。dd 最大不超过几十,递归深度同样安全。
  • Python 与 C++ 的关系:main.py 是同一套 IDA*(增量断点数 + 同长跳过),复杂度同阶, 只是常数大一个数量级:同样 t=5t = 5、n=23n = 23 的最坏用例 0.090.09 s, 本地 10 个测试点最大 0.060.06 s。C++ 侧要注意的是把估价更新写成增量式, 否则每层重扫一遍排列会白白多一个 O(n)O(n)。

总结

  • 一次操作只改一处邻接:块内相邻对的差的绝对值在翻转下不变,所以"断点数"每步至多减 1。 这是本题估价函数的全部依据,也是可采纳性的证明。
  • 哨兵把下界和达成条件焊在一起:补上虚拟的 n+1n+1 之后,“断点数为 00” 与"已经升序"完全等价 (不补的话,完全逆序也会让下界归零),判定变成 O(1)O(1)。
  • 迭代加深而非 BFS:状态数 n!n! 无法展开,而 IDA* 只花 O(n)O(n) 空间, 且"首个成功的深度上限就是答案"——比它小的上限都已排除。
  • 常数级的剪枝也要捡:跳过与上一步同长度的翻转(纯撤销)、增量维护估价函数, 这两条不改变复杂度阶数,却直接决定 Python 版能不能跑完。
  • 本题的答案就是排列的"煎饼距离"(pancake distance)。用 BFS 穷举验证过:n⩽9n \leqslant 9 的全部 排列(n=9n = 9 有 362880 个)本解法都给出精确最小值,且 n⩽9n \leqslant 9 的最大答案 0,1,3,4,5,7,8,9,100,1,3,4,5,7,8,9,10 与已知的煎饼数 P(n)P(n) 一致;n=9∼23n = 9 \sim 23 的随机数据也与仓库内另一份 独立实现(只数内部邻接、显式比对升序)逐点一致。
  • 关于本题数据:仓库里本题的 data/ 是 data.py 现场生成的(生成脚本的注释把"完全逆序" 说成需要 2n−32n-3 步,这是错的——逆序一步翻整串即可归位,数据中 n=21,23n = 21, 23 的逆序用例答案正是 11),题面也是按原始提示里 25 个测试点的细分方案重建成 10 个点的。所以"出题意图"与最初的 测试点划分并非一一对应;本解只按题面给出的最优化目标(最少操作次数)实现,不依赖测试点的分组方式。