UVa 140 (枚举排列) Bandwidth

题意较复杂，请参见原题=_=||

没什么好说的，直接枚举每个排列就好了，然后记录最小带宽，以及对应的最佳排列。

STL里的next_permutation函数真是好用。

比较蛋疼的就是题目的输入了。。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int maxn = 10;
 5 
 6 int id[256], letter[maxn];
 7 char in[1000];
 8 
 9 int main()
10 {
11     //freopen("in.txt", "r", stdin);
12 
13     while(scanf("%s", in) == 1 && in[0] != '#')
14     {
15         int n = 0;
16         for(char ch = 'A'; ch <= 'Z'; ++ch)
17             if(strchr(in, ch) != NULL)
18             {
19                 id[ch] = n;
20                 letter[n++] = ch;
21             }
22 
23         int l = strlen(in), p = 0, q = 0;
24         vector<int> u, v;
25         for(;;)
26         {
27             while(p < l && in[p] != ':') p++;
28             if(p == l) break;
29             while(q < l && in[q] != ';') q++;
30             for(int i = p+1; i < q; ++i)
31             {
32                 u.push_back(id[in[p-1]]);
33                 v.push_back(id[in[i]]);
34             }
35             p++; q++;
36         }
37 
38         int P[maxn], bestP[maxn], pos[maxn], ans = n;
39         for(int i = 0; i < n; ++i) P[i] = i;
40         do
41         {
42             for(int i = 0; i < n; ++i) pos[P[i]] = i;
43             int bandwidth = 0;
44             for(int i = 0; i < u.size(); ++i) bandwidth = max(bandwidth, abs(pos[u[i]] - pos[v[i]]));
45             if(bandwidth < ans)
46             {
47                 ans = bandwidth;
48                 memcpy(bestP, P, sizeof(P));
49             }
50         }while(next_permutation(P, P+n));
51 
52         for(int i = 0; i < n; ++i) printf("%c ", letter[bestP[i]]);
53         printf("-> %d
", ans);
54     }
55 
56     return 0;
57 }
58 
59 代码君

代码君