|
|
|
|
|
## [$AcWing$ $180$ 排书](https://www.acwing.com/problem/content/182/)
|
|
|
|
|
|
|
|
|
|
|
|
### 一、题目描述
|
|
|
|
|
|
给定 $n$ 本书，编号为 $1$∼$n$。
|
|
|
|
|
|
|
|
|
|
|
|
在初始状态下，书是任意排列的。
|
|
|
|
|
|
|
|
|
|
|
|
在每一次操作中，可以 **抽取其中连续的一段**，再把这段 **插入到其他某个位置**。
|
|
|
|
|
|
|
|
|
|
|
|
我们的目标状态是把书按照 $1$∼$n$ 的顺序依次排列。
|
|
|
|
|
|
|
|
|
|
|
|
**求最少需要多少次操作。**
|
|
|
|
|
|
|
|
|
|
|
|
**输入格式**
|
|
|
|
|
|
第一行包含整数 $T$，表示共有 $T$ 组测试数据。
|
|
|
|
|
|
|
|
|
|
|
|
每组数据包含两行，第一行为整数 $n$，表示书的数量。
|
|
|
|
|
|
|
|
|
|
|
|
第二行为 $n$ 个整数，表示 $1$∼$n$ 的一种任意排列。
|
|
|
|
|
|
|
|
|
|
|
|
同行数之间用空格隔开。
|
|
|
|
|
|
|
|
|
|
|
|
**输出格式**
|
|
|
|
|
|
每组数据输出一个最少操作次数。
|
|
|
|
|
|
|
|
|
|
|
|
如果最少操作次数大于或等于 $5$ 次，则输出 $5~ or~ more$。
|
|
|
|
|
|
|
|
|
|
|
|
每个结果占一行。
|
|
|
|
|
|
|
|
|
|
|
|
**数据范围**
|
|
|
|
|
|
$1≤n≤15$
|
|
|
|
|
|
|
|
|
|
|
|
**输入样例**：
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
3
|
|
|
|
|
|
6
|
|
|
|
|
|
1 3 4 6 2 5
|
|
|
|
|
|
5
|
|
|
|
|
|
5 4 3 2 1
|
|
|
|
|
|
10
|
|
|
|
|
|
6 8 5 3 4 7 2 9 1 10
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
**输出样例**：
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
2
|
|
|
|
|
|
3
|
|
|
|
|
|
5 or more
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
### 二、解题思路
|
|
|
|
|
|
|
|
|
|
|
|
先考虑每一步的决策数量：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
其中$$\large len \in [1,n-1]$$
|
|
|
|
|
|
|
|
|
|
|
|
#### 1. 总结规律
|
|
|
|
|
|
> **① 当抽取长度为 $len$ 的一段时，有 $n−len+1$ 种抽法**
|
|
|
|
|
|
> **解释**：比如$n=9,len=3$,我们发现，可以有$7$种抽法，也就是$9-3+1=7$,抽象一下:
|
|
|
|
|
|
>
|
|
|
|
|
|
> **② 对于每种抽法，有 $n−len$ 种放法**
|
|
|
|
|
|
> **解释**：原来共$n$个小球，去掉$len$个后，剩下$n-len$个，那么中间共$n-len-1$个空挡，再加上左右的 边界，就是$n-len+1$个，但原来的位置视为是一种放法， 也就是有$n-len$个位置可以更换
|
|
|
|
|
|
> **③ 将某一段向后移动，等价于将跳过的那段向前移动**
|
|
|
|
|
|
> **④ 将某一段向前移动，等价于将跳过的那段向后移动**
|
|
|
|
|
|
|
|
|
|
|
|
#### 2. 总的分支数量
|
|
|
|
|
|
由于两段交换可以是左到右，也可是右到左
|
|
|
|
|
|
|
|
|
|
|
|
**每种移动方式被算了两遍**，所以 **每个状态总共的分支数量** 还需要除以$2$：$$\sum_{len=1}^{n-1}(n−len+1)\times (n−len)/2=(15∗14+14∗13+…+2∗1)/2=560$$
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
按迭代加深思路思考，如果在 **四步以内解决**，**最多** 有 $560 \times 560 \times 560 \times 560 =560^4=98~344~960~000 > 1e8$ 个状态，会超时。
|
|
|
|
|
|
|
|
|
|
|
|
若使用双向 $BFS$ 或双向 $DFS$，状态数可降至 $10^5$。由于 **估价函数** 较为简单，且答案在浅层，还可使用 $A∗$ 或 $IDA∗$ 加强剪枝效果，此处使用后者。
|
|
|
|
|
|
|
|
|
|
|
|
#### 3. 迭代加深 $+$ 估值函数$=IDA*$
|
|
|
|
|
|
|
|
|
|
|
|
<font color='red' size=4><b>① 估值函数</b></font>
|
|
|
|
|
|
**估价函数的值 = 当前状态离目标状态的真实距离的最小值**，一旦已搜索的深度$u$加上估价函数的值 **超过** 了设定的深度，停止搜索。
|
|
|
|
|
|
|
|
|
|
|
|
如果每次只移动一个元素，可以 **用每个元素离最终位置的距离作为估价函数**，但是现在是批量移动元素。比如`1 2 3 4 5`，将`2 3`移动到`4`的后面得到`1 4 2 3 5`，可以发现`1`的后继、`4`的后继、`3`的后继都改变了，而其它元素的后继未变，实际上，**每次移动最多能改变三个元素的后继**。
|
|
|
|
|
|
|
|
|
|
|
|
**最终状态是每个元素的后继都比当前元素多`1`，此时有序。**
|
|
|
|
|
|
|
|
|
|
|
|
设 **估价函数为错误后继的对数**，只要一个元素的后一个元素不是比它大`1`的元素，就记入错误后继。既然一次移动只能改变`3`个元素的后继，那么当前错误后继对数为`cnt`时，至少需要 $⌈cnt / 3⌉$ 次移动才能将序列恢复为有序。
|
|
|
|
|
|
|
|
|
|
|
|
$$\large f=(cnt + 2) / 3$$
|
|
|
|
|
|
> 这里加上$2$是为了**上取整**
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
<font color='red' size=4><b>② 三次翻转实现子串移动、还原现场</b></font>
|
|
|
|
|
|
下面要做的，就是在$dfs$里枚举
|
|
|
|
|
|
- $len$ : 序列长度
|
|
|
|
|
|
- $start$ : 起点位置
|
|
|
|
|
|
- $pos$ : 移动到哪个位置后
|
|
|
|
|
|
>比如 `1 2 3 4 5`，长度为`1`时，起点是下标为`0`的位置，也就是元素`1`，将它移动到下标为`3`的后面就得到了`2 3 4 1 5`。长度为`1`的序列移动规律可能不太明显，来看个更长的序列，`1 2 3 4 5 6 7 8`移动`2 3 4`到`6`的后面得到`1 5 6 2 3 4 7 8`，可以发现只是将`2 3 4`右移了`2`个位置。这里我使用了一种 **常见** 的移动元素的策略，就是先将`2 3 4`反转，再将`5 6`反转，最后将这个`5`个元素所在区间的所有元素反转，即`1 2 3 4 5 6 7 8`到`1 4 3 2 5 6 7 8`到`1 4 3 2 6 5 7 8`到`1 5 6 2 3 4 7 8`，也就实现了将序列右移的目的。
|
|
|
|
|
|
|
|
|
|
|
|
这个需要提前熟悉相关翻转、还原的知识，否则直接写代码就开始怀疑人生了：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
|
|
|
|
|
|
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
|
|
|
|
|
|
|
|
|
|
|
|
void print() {
|
|
|
|
|
|
for (int i = 0; i < 10; i++) cout << a[i] << " ";
|
|
|
|
|
|
cout << endl;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
int main() {
|
|
|
|
|
|
// 将数组中一段234位置与56互换
|
|
|
|
|
|
// 学习一下常见的移动元素的策略,实现了将序列右移的目的。
|
|
|
|
|
|
|
|
|
|
|
|
int st = 1; // 开始下标
|
|
|
|
|
|
int ed = 5; // 结束下标 len=(ed-st+1)，共(5-1+1)=5个
|
|
|
|
|
|
int len = 3; // 前半段串的长度
|
|
|
|
|
|
|
|
|
|
|
|
//(1)将234反转
|
|
|
|
|
|
reverse(a + st, a + st + len); // 参数：开始的数组索引，开始数组索引+要翻转的长度,这是一个前闭后开的区间[)
|
|
|
|
|
|
print();
|
|
|
|
|
|
|
|
|
|
|
|
//(2)将56反转
|
|
|
|
|
|
reverse(a + st + len, a + ed + 1); // 时刻注意前闭后开
|
|
|
|
|
|
print();
|
|
|
|
|
|
|
|
|
|
|
|
//(3)将23456反转
|
|
|
|
|
|
reverse(a + st, a + ed + 1); // 整个区间翻转，就实现了两个子串互换位置的目标
|
|
|
|
|
|
print();
|
|
|
|
|
|
// 输出：1 5 6 2 3 4 7 8 9 10
|
|
|
|
|
|
// 与预期结果一致
|
|
|
|
|
|
|
|
|
|
|
|
puts("");
|
|
|
|
|
|
|
|
|
|
|
|
// 尝试再反转回来
|
|
|
|
|
|
// 后串长度：
|
|
|
|
|
|
reverse(a + st, a + ed + 1 - len);
|
|
|
|
|
|
print();
|
|
|
|
|
|
|
|
|
|
|
|
reverse(a + ed - len + 1, a + ed + 1);
|
|
|
|
|
|
print();
|
|
|
|
|
|
|
|
|
|
|
|
reverse(a + st, a + ed + 1);
|
|
|
|
|
|
print();
|
|
|
|
|
|
// 输出：1 2 3 4 5 6 7 8 9 10
|
|
|
|
|
|
// 与预期结果一致
|
|
|
|
|
|
return 0;
|
|
|
|
|
|
}
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
### 三、$IDA* Code$
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 16; // 1≤n≤15
|
|
|
|
|
|
int a[N]; // 记录书的排列情况
|
|
|
|
|
|
int n; // 书的数量
|
|
|
|
|
|
int depth; // 最少的操作步数
|
|
|
|
|
|
|
|
|
|
|
|
// 估值函数:实时计算此状态到终止状态最少的步数
|
|
|
|
|
|
// 这个IDA*的估价函数，本质上与A*的是一样的意思，都是在每个状态下可以获取到距离理想状态（即每个数字后序都大1）的错误后继个数
|
|
|
|
|
|
int f() {
|
|
|
|
|
|
int cnt = 0;
|
|
|
|
|
|
// 计算前后非+1递增的 错误后继的对数
|
|
|
|
|
|
for (int i = 0; i < n - 1; i++)
|
|
|
|
|
|
if (a[i] + 1 != a[i + 1]) cnt++;
|
|
|
|
|
|
return (cnt + 2) / 3; // 每次移动，最多能解决三个错误后继，如果现在有cnt个错误后继，最少需要 ⌈cnt/3⌉次操作
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
// u:已经操作的步数
|
|
|
|
|
|
bool dfs(int u) {
|
|
|
|
|
|
int t = f(); // 未来最小的操作步数
|
|
|
|
|
|
if (t == 0) return true; // 已完成排序
|
|
|
|
|
|
if (u + t > depth) return false; // 当前操作步数+未来预期最小> 迭代加深的深度 表示没有找到结果，返回。及时剪枝
|
|
|
|
|
|
|
|
|
|
|
|
for (int len = 1; len < n; len++) { // 枚举抽取长度
|
|
|
|
|
|
// 枚举每次抽取的开始索引下标,注意一下开始索引+长度不能超过n-1,即<n
|
|
|
|
|
|
// st: 起始下标
|
|
|
|
|
|
for (int st = 0; st + len <= n; st++) {
|
|
|
|
|
|
// 与另外哪个子序列进行对调？也就是向右移动多少个位置
|
|
|
|
|
|
for (int ed = st + len; ed < n; ed++) {
|
|
|
|
|
|
// 序列右移
|
|
|
|
|
|
reverse(a + st, a + st + len);
|
|
|
|
|
|
reverse(a + st + len, a + ed + 1);
|
|
|
|
|
|
reverse(a + st, a + ed + 1);
|
|
|
|
|
|
|
|
|
|
|
|
// 本轮实现了一次右移，那么，这条路线是否可以成功抵达终点，就依赖于我的后续子孙了
|
|
|
|
|
|
if (dfs(u + 1)) return true;
|
|
|
|
|
|
|
|
|
|
|
|
// 后面串的长度,还原现场,回溯
|
|
|
|
|
|
reverse(a + st, a + ed + 1 - len);
|
|
|
|
|
|
reverse(a + ed + 1 - len, a + ed + 1);
|
|
|
|
|
|
reverse(a + st, a + ed + 1);
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
return false;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
// AC 204 ms
|
|
|
|
|
|
int main() {
|
|
|
|
|
|
int T; // T组测试数据
|
|
|
|
|
|
scanf("%d", &T);
|
|
|
|
|
|
while (T--) {
|
|
|
|
|
|
scanf("%d", &n); // 表示书的数量
|
|
|
|
|
|
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
|
|
|
|
|
|
/*
|
|
|
|
|
|
最少操作次数
|
|
|
|
|
|
解释：因为可能书本来天生就是有序，即每本书n后面都是n+1，完全合格的顺序，这时不用调整，最少操作数为0
|
|
|
|
|
|
需要从0开始查询最少操作次数
|
|
|
|
|
|
*/
|
|
|
|
|
|
depth = 0;
|
|
|
|
|
|
while (depth < 5 && !dfs(0)) depth++; // 有层数限制的dfs，迭代加深
|
|
|
|
|
|
|
|
|
|
|
|
if (depth >= 5) // 最少操作次数大于或等于5次
|
|
|
|
|
|
puts("5 or more");
|
|
|
|
|
|
else
|
|
|
|
|
|
printf("%d\n", depth); // 最少操作次数
|
|
|
|
|
|
}
|
|
|
|
|
|
return 0;
|
|
|
|
|
|
}
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
### 四、$A*$(优化版本$bfs$)
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
#include <cstdio>
|
|
|
|
|
|
#include <cstring>
|
|
|
|
|
|
#include <unordered_set>
|
|
|
|
|
|
#include <queue>
|
|
|
|
|
|
#include <algorithm>
|
|
|
|
|
|
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
typedef unsigned long long ULL; //自动溢出的ULL，计算整数数组的HASH值
|
|
|
|
|
|
const int B = 17; // 17进制，用于HASH计算，这是大于15的第一个质数
|
|
|
|
|
|
const int N = 15;
|
|
|
|
|
|
int n;
|
|
|
|
|
|
unordered_set<ULL> b; //用于检测一个状态是否已经访问过了
|
|
|
|
|
|
|
|
|
|
|
|
struct Node {
|
|
|
|
|
|
int v[N]; //当前的状态
|
|
|
|
|
|
int step; //步数
|
|
|
|
|
|
int f; //估值
|
|
|
|
|
|
bool operator<(const Node &x) const { //重载小于号
|
|
|
|
|
|
return x.f < f;
|
|
|
|
|
|
}
|
|
|
|
|
|
} x;
|
|
|
|
|
|
|
|
|
|
|
|
//优先队列
|
|
|
|
|
|
priority_queue<Node> q;
|
|
|
|
|
|
|
|
|
|
|
|
//检测是否到了目标状态
|
|
|
|
|
|
bool check(Node x) {
|
|
|
|
|
|
for (int i = 0; i < n; i++)
|
|
|
|
|
|
if (x.v[i] != i + 1) return false;
|
|
|
|
|
|
return true;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
// 计算数组状态的hash值
|
|
|
|
|
|
ULL getHash(Node x) {
|
|
|
|
|
|
ULL res = 0;
|
|
|
|
|
|
for (int i = 0; i < n; i++) res = res * B + x.v[i];
|
|
|
|
|
|
return res;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
//估值函数，1次变更，可以最多修改3个后继，现在有res个后继，最少的修改次数是 ⌊res/3⌋=(res+3-1)/3
|
|
|
|
|
|
int f(Node x) {
|
|
|
|
|
|
int res = 0;
|
|
|
|
|
|
for (int i = 1; i < n; i++)
|
|
|
|
|
|
if (x.v[i] != x.v[i - 1] + 1) res++;
|
|
|
|
|
|
return (res + 2) / 3;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
// AStar
|
|
|
|
|
|
int bfs() {
|
|
|
|
|
|
while (q.size()) {
|
|
|
|
|
|
Node u = q.top(); //取出当前状态
|
|
|
|
|
|
q.pop();
|
|
|
|
|
|
|
|
|
|
|
|
if (u.f >= 5) return 5; //当前状态无法在5步之内到达终点，返回无结果
|
|
|
|
|
|
if (check(u)) return u.step; //如果第一次获取到了一个成功的状态，返回当前步数
|
|
|
|
|
|
|
|
|
|
|
|
for (int len = 1; len < n; len++) { //枚举长度
|
|
|
|
|
|
for (int st = 0; st + len - 1 < n; st++) { //枚举起始坐标
|
|
|
|
|
|
for (int ed = st + len; ed < n; ed++) {
|
|
|
|
|
|
//抄出来
|
|
|
|
|
|
memcpy(x.v, u.v, sizeof u.v);
|
|
|
|
|
|
|
|
|
|
|
|
//三次翻转，子串对调
|
|
|
|
|
|
reverse(x.v + st, x.v + st + len);
|
|
|
|
|
|
reverse(x.v + st + len, x.v + ed + 1);
|
|
|
|
|
|
reverse(x.v + st, x.v + ed + 1);
|
|
|
|
|
|
|
|
|
|
|
|
//如果此状态已经进过优先队列，那么放弃掉
|
|
|
|
|
|
ULL hash = getHash(x);
|
|
|
|
|
|
if (b.count(hash)) continue;
|
|
|
|
|
|
//记录使用过
|
|
|
|
|
|
b.insert(hash);
|
|
|
|
|
|
|
|
|
|
|
|
//修改步数
|
|
|
|
|
|
x.step = u.step + 1;
|
|
|
|
|
|
//计算h值 h = g + f
|
|
|
|
|
|
x.f = x.step + f(x);
|
|
|
|
|
|
//入队列
|
|
|
|
|
|
q.push(x);
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
return 5;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
// AC 279 ms
|
|
|
|
|
|
int main() {
|
|
|
|
|
|
int T;
|
|
|
|
|
|
scanf("%d", &T);
|
|
|
|
|
|
while (T--) {
|
|
|
|
|
|
//清空Hash表
|
|
|
|
|
|
b.clear();
|
|
|
|
|
|
//清空优先队列,清空优先队列的一个小技巧
|
|
|
|
|
|
q = {};
|
|
|
|
|
|
|
|
|
|
|
|
scanf("%d", &n);
|
|
|
|
|
|
|
|
|
|
|
|
//初始状态入队列
|
|
|
|
|
|
for (int i = 0; i < n; i++) scanf("%d", &x.v[i]); //当前的数组状态
|
|
|
|
|
|
x.step = 0; //原始状态，步数为0
|
|
|
|
|
|
x.f = f(x); //到达终点的最少步数估值
|
|
|
|
|
|
|
|
|
|
|
|
q.push(x); //对象入队列
|
|
|
|
|
|
b.insert(getHash(x)); //记录此状态已使用
|
|
|
|
|
|
|
|
|
|
|
|
int res = bfs(); // A*寻路
|
|
|
|
|
|
|
|
|
|
|
|
if (res >= 5)
|
|
|
|
|
|
puts("5 or more");
|
|
|
|
|
|
else
|
|
|
|
|
|
printf("%d\n", res);
|
|
|
|
|
|
}
|
|
|
|
|
|
return 0;
|
|
|
|
|
|
}
|
|
|
|
|
|
```
|
