UVa 10570 外星人聚会

题意：
输入1~n的排列，每次可以交换两个整数，求出最少交换次数使之变成有序的环状序列。

思路：
主要的解题方法就是寻找置换环，举个例子来说吧，因为起点可以是任意位置，我们假设起点在1的位置。

比如说 5 1 3 4 2 7 6 8 ，第一个数5应该在第5个位置，此时第5个位置上为2，而2应该在第2个位置，此时第2个位置上为1，而1应该在第一个位置即5的位置。因此{5,1,2}构成了一个置换群，别的也是这样的分析，总共可以分为{5,1,2}，{3}，{4}，{6,7}，{8}5个置换环，所以交换次数为8-5=3。这个也很好理解，如果每个数都在正确的位置上，那么每个数各自构成一个置换环，那么相减之后就是0了。

 1 #include<iostream> 
 2 #include<cstring>
 3 #include<string>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 int n;
 8 int a[1100],b[1100];
 9 int vis[1100];
10 
11 void dfs(int k, int start)
12 {
13     if (vis[k])     return;
14     vis[k] = 1;
15     int t = a[k + start];
16     dfs(t, start);
17 }
18 
19 void dfs2(int k, int start)
20 {
21     if (vis[k])     return;
22     vis[k] = 1;
23     int t = a[start-k];
24     dfs2(t, start);
25 }
26 
27 int main()
28 {
29     //freopen("D:\txt.txt", "r", stdin);
30     while (cin >> n && n)
31     {
32         int num;
33         for (int i = 0; i < n; i++)
34         {
35             cin >> a[i];
36             a[i + n] = a[i];
37         }
38         int count = 0;
39 
40         //正序
41         for (int i = 0; i < n; i++)   //枚举起点
42         {
43             memset(vis, 0, sizeof(vis));
44             num = 0;
45             for (int j = 0; j < n; j++)
46             {
47                 if (!vis[j])
48                 {
49                     num++;
50                     dfs(j, i);
51                 }
52             }
53             count = max(num, count);
54         }
55 
56         //逆序
57         for (int i = 2 * n - 1; i >= n;i--)   //枚举起点
58         {
59             memset(vis, 0, sizeof(vis));
60             num = 0;
61             for (int j = 0; j < n; j++)
62             {
63                 if (!vis[j])
64                 {
65                     num++;
66                     dfs2(j, i);
67                 }
68             }
69             count = max(num, count);
70         }
71         int ans = n - count;
72         cout << ans << endl;
73     }
74 }