Loading... # ACWing 180 排书 题解 ## 题目描述 给定$n$本书，编号为$1∼n$。 在初始状态下，书是任意排列的。 在每一次操作中，可以抽取其中连续的一段，再把这段插入到其他某个位置。 我们的目标状态是把书按照$1∼n$的顺序依次排列。 求最少需要多少次操作。 ## 输入 第一行包含整数$T$，表示共有$T$组测试数据。 每组数据包含两行，第一行为整数$n$，表示书的数量。 第二行为$n$个整数，表示$1∼n$的一种任意排列。 同行数之间用空格隔开。 ## 输出 每组数据输出一个最少操作次数。 如果最少操作次数大于或等于$5$次，则输出 `5 or more`。 每个结果占一行。 ## 解题思路 首先观察到最小操作次数小于5次， 因此可以考虑使用迭代加深进行搜索 但不难发现， 每层DFS的最大搜索数量的计算如下： - 假设插入到字符串中第$i$个字符所在的位置， 则考虑到对称性， 可能被插入的字符串有$\frac{i^2}{2}$中选择， 因此一层遍历的总的搜索数量为$\sum_1^{len}\frac{i^2}{2} = \frac{len*(len + 1) * (2 * len + 1)}{12}$， 在$n=15$时可以到达$562$左右的大小， 显然$562^4$会超时 因此不难判断， 使用迭代加深搜索不可取 因此可以采用启发式搜索减少分支数量： - 不难发现， 当书本全部依次排列时， 对于任意位置都满足`a[i + 1] == a[i]` - 记`f()`为书本中满足`a[i + 1] != a[i]`的位置的个数 - 只要书本中存在乱序， 就一定有`f() >= 2` - 每一次更改书本的位置时， 设连续的一段书是起点为`l`， 终点为`r`的一摞书， 将他们插入`k`的位置， 则改变了`a[l]`， `a[r + 1]`， `a[k + 1]`和他们的前驱书本之间的关系， 对于其他的均没有改变 - 假设当前相邻书本之间乱序的数目为$t$， 每一次最多修复三个乱序， 所有的乱序需要至少$\lceil \frac{t}{3}\rceil$次才可以完全更新 - 因此如果深度加上至少需要更新的次数已经大于等于最大的深度， 则一定没有解 ## AC代码 ```cpp #include <cstdio> #include <cstdlib> #include <iostream> #include <vector> #include <cstring> #define endl '\n' using namespace std; const int N = 20; int t; int n; int a[N]; int backup[5][N]; int f() { int cnt = 0; for(int i = 2; i <= n; i ++) { if(a[i - 1] + 1 != a[i]) cnt ++; } return cnt; } bool dfs(int u, int depth) { int t = f(); if(u + (t + 2) / 3 > depth) return false; if(!t) return true; for(int len = 1; len <= n; len ++) { for(int l = 1; l + len - 1 <= n; l ++) { int r = l + len - 1; for(int k = r + 1; k <= n; k ++) { memcpy(backup[u], a, sizeof a); int x, y; for(x = r + 1, y = l; x <= k; x ++, y ++) a[y] = backup[u][x]; for(x = l; x <= r; x ++, y ++) a[y] = backup[u][x]; if(dfs(u + 1, depth)) return true; memcpy(a, backup[u], sizeof a); } } } return false; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> t; while(t --) { cin >> n; for(int i = 1; i <= n; i ++) cin >> a[i]; int depth = 0; while(depth < 5 && !dfs(0, depth)) depth ++; if(depth == 5) cout << "5 or more" << endl; else cout << depth << endl; } return 0; } ``` 最后修改：2025 年 03 月 07 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏