题目大意：输入n，表示已知n组rankings，每组ranking包括五个小组(A、B、C、D和E)。定义distance为两个ranking之间，不同小组相对排名不同的个数的和。定义value为某个ranking跟n组rankings的distance的和。使得value最小的ranking称为median ranking。求每组输入的median rankin和value，n为0则终止。
解题思路：全排列五个小组的ranking组合，计算每个组合的value，找到最小的median ranking。全排列用递归的思想，第一层放A，第二层放B，第三层放C，第四层放D，第五层放E。计算distance时用一个数组记录组合中元素的相对顺序，算是小许优化。
代码如下：
1 #include <cstdio> 2 #include <cstring> 3 #include <climits> 4 5 const int LEN = 6; 6 const int MAXN = 101; 7 char strs[MAXN][LEN]; 8 char ans[LEN]; 9 char temp[LEN]; 10 int cor[LEN]; 11 int value; 12 int n; 13 14 void init() { 15 value = INT_MAX; 16 for (int i = 0; i < LEN; i++) { 17 temp[i] = ‘\0‘; 18 } 19 } 20 21 void dfs(int k) { 22 if (k == LEN - 1) { 23 for (int i = 0; i < LEN - 1; i++) { 24 cor[temp[i] - ‘A‘] = i; 25 } 26 27 int v = 0; 28 for (int m = 0; m < n; m++) { 29 for (int i = 0; i < LEN - 1; i++) { 30 for (int j = i + 1; j < LEN - 1; j++) { 31 if (cor[strs[m][i] - ‘A‘] > cor[strs[m][j] - ‘A‘]) { 32 v++; 33 } 34 } 35 } 36 } 37 38 if (v < value) { 39 value = v; 40 for (int i = 0; i < LEN; i++) { 41 ans[i] = temp[i]; 42 } 43 } 44 45 // printf("STR: %s VALUE: %d\n", temp, v); 46 47 return; 48 } 49 50 for (int i = 0; i < LEN - 1; i++) { 51 if (temp[i] == ‘\0‘) { 52 temp[i] = ‘A‘ + k; 53 dfs(k + 1); 54 temp[i] = ‘\0‘; 55 } 56 } 57 } 58 59 int main() { 60 while (scanf("%d", &n), n) { 61 62 init(); 63 64 for (int i = 0; i < n; i++) { 65 scanf("%s", strs[i]); 66 } 67 68 dfs(0); 69 70 printf("%s is the median ranking with value %d.\n", ans, value); 71 72 } 73 return 0; 74 }
原文：http://www.cnblogs.com/mchcylh/p/4857125.html