Description
给定一个 $1∼n$的排列 $x$，每次你可以将 $x_1∼x_i$ 翻转。试求将序列变为升序的最小操作次数，单个测试点内有 $T$ 组数据。
数据随机。
Solution
其实原题并没有说数据是随机的，然而在非随机数据下，本题不存在可行的解法。Hack 数据：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| //By lxl
in：
5
25
1 25 23 24 19 20 15 16 11 12 7 8 3 4 2 6 5 10 9 14 13 18 17 22 21
25
1 25 23 24 19 20 15 16 11 12 7 8 3 4 2 6 5 10 9 14 13 18 17 22 21
25
1 25 23 24 19 20 15 16 11 12 7 8 3 4 2 6 5 10 9 14 13 18 17 22 21
25
1 25 23 24 19 20 15 16 11 12 7 8 3 4 2 6 5 10 9 14 13 18 17 22 21
25
1 25 23 24 19 20 15 16 11 12 7 8 3 4 2 6 5 10 9 14 13 18 17 22 21
out:
19
19
19
19
19
|
本题的官方题解没有任何的时间复杂度分析，我认为这是一种极其不负责任的行为。关于本题接下来的讨论，皆基于数据随机的基础上。
考虑迭代加深。官方题解中说答案不超过 $2(n - 1)$。实际上，根据小数据的实际测试，答案的上界实际上是达不到 $2(n - 1)$ 的，这是官方题解中另一个不负责任的行为。
考虑搜索剪枝。发现一次翻转最多能让相邻两个数的差的绝对值为 1 的对数减少 1，于是当当前步数 $cnt$ + 相邻两个数的差的绝对值不为 1 的对数 $now$ > 限制步数 $limit$ 时直接退出搜索即可。
经过大量的随机数据检验，我们有理由相信这份代码在随机数据下表现优秀。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
| #include <cstdio>
#define maxN 30
int n = 0;
int a[maxN];
int abs (int x)
{
return x >= 0 ? x : (-x);
}
void change (int x)
{
int l = 1, r = x;
while(l < r)
{
int t = a[l];
a[l] = a[r];
a[r] = t;
l++, r--;
}
}
bool dfs (int limit, int cnt)
{
int i = n;
for(;i >= 1; i--)
{
if(a[i] != i)
{
break;
}
}
if(!i)
{
return true;
}
const int maxI = i;
int now = 0;
for(i = 1;i <= maxI; i++)
{
if(abs(a[i] - a[i + 1]) != 1)
{
now++;
}
}
if(cnt == limit || now + cnt > limit)
{
return false;
}
for(i = 1;i <= maxI; i++)
{
change(i);
if(dfs(limit, cnt + 1))
{
return true;
}
change(i);
}
return false;
}
int main ()
{
int T = 0;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
for(int i = 1;i <= n; i++)
{
scanf("%d", &a[i]);
}
const int N = (n << 1);
for(int i = 0;i <= N; i++)
{
if(dfs(i, 0))
{
printf("%d\n", i);
break;
}
}
}
return 0;
}
|