WHU 1552 Seats 枚举

题意：

　　有一个年级中7个班的n个学生。

　　一天，他们毫无顺序的站成一排。请计算最小的交换次数，使得相同班的同学都站在一起。（只有站在一起的人才能交换）

思路：

　　如果知道班级的最终排列就能在很短的时间里，计算出所需的交换次数。那么，我们只需要枚举排列即可。

　　如果，a班的一个人要走到前面，那么，他必须和他前面所有其他班的人交换。

　　所以，先预处理出一个数组 f[i][j] 表示每个 i 班的前面的 j 班同学的总和。然后就可以在m(班级数) * m 的时间里求出排列需要交换的次数。

代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 
 7 typedef long long ll;
 8 
 9 const int MAXN = (int) 1e5+5;
10 const ll INF = (ll)1<<60;
11 
12 ll f[8][8], sum[8]; //f[i][j] : i 前面有多少个 j
13 int a[MAXN];
14 int n;
15 ll ans;
16 bool vis[8];
17 int od[8];
18 
19 void cal() {
20     ll res = 0;
21     for (int i = 1; i < 8; i++) {
22         for (int j = 0; od[j]!=i; j++) {
23             res += f[i][od[j]];
24         }
25     }
26     ans = min(ans, res);
27 }
28 
29 void dfs(int cnt) {
30     if (7==cnt) {
31         cal();
32         return ;
33     }
34     for (int i = 1; i < 8; i++) if (!vis[i]) {
35         vis[i] = true;
36         od[cnt] = i;
37         dfs(cnt+1);
38         vis[i] = false;
39     }
40 }
41 
42 void print() {
43     for (int i = 1; i < 8; i++) {
44         for (int j = 1; j < 8; j++)
45             printf("%d ", f[i][j]);
46         puts("");
47     }
48 }
49 
50 int main() {
51     #ifdef Phantom01
52         freopen("WHU1552.in", "r", stdin);
53     #endif // Phantom01
54 
55     while (scanf("%d", &n)!=EOF) {
56         memset(vis, false, sizeof(vis));
57         memset(f, 0, sizeof(f));
58         memset(sum, 0, sizeof(sum));
59         for (int i = 0; i < n; i++) {
60             scanf("%d", &a[i]);
61             sum[a[i]]++;
62             for (int j = 1; j < 8; j++) {
63                 f[a[i]][j] += sum[j];
64             }
65         }
66 //        print();
67         ans = INF;
68         dfs(0);
69         printf("%lld
", ans);
70     }
71 
72     return 0;
73 }

View Code

p.s.:当时比赛的时候有想到过枚举排列，但是不知道该怎么很快的计算交换次数，所以就没写。收集信息和组合信息的能力还不够啊……