Sicily 1006. Team Rankings 解题报告

思路：

　　ABCDE总共只有120种排列，现在要找到字典序最小的那个，可以一个一个进行实验，算出每个与所有输入的距离和，找出距离和最小那个即可。生成全排列这里直接从12345加到54321，将其中的120个要的排列记录下来，代表ABCDE的字典序全排列。

　　计算两个排列的距离，可以考虑先用数组记录每个字母出现的位置，如BCAED和ACBDE，用数组31254和13245记录。开头两位31和13说明AB的顺序相反，距离加1，然后依次类推可以算出整个距离。

代码：

 1 #include<iostream>
 2 #include<sstream>
 3 #include<stdio.h>
 4 #include<memory.h>
 5 using namespace std;
 6 
 7 
 8 string permutation[120];
 9 
10 void create_permutation();
11 bool is_valid(string s);
12 int get_value(string *rankings,int i,int n);
13 int get_a_value(string s1,string s2);
14 
15 int main(){
16     int n;
17     create_permutation();
18     while(cin >> n && n != 0){
19         string rankings[n];
20         for(int i = 0;i < n;i++){
21             cin >> rankings[i];
22         }
23         int position = 0,median_ranking = get_value(rankings,0,n);
24         for(int i = 1;i < 120;i++){
25             if(get_value(rankings,i,n) < median_ranking){
26                 position = i;
27                 median_ranking = get_value(rankings,i,n);
28             }
29         }
30         for(int i = 0;i < 5;i++)
31             printf("%c",permutation[position][i] - '1' + 'A');
32         cout << " is the median ranking with value " << median_ranking << '.' << endl;
33     }
34     return 0;
35 }
36 void create_permutation(){
37     //Post:permutation of ABCDE has been created.12345 means ABCDE.
38     int count = 0;
39     for(int i = 12345;i <= 54321;i++){
40         stringstream ss;
41         string s;
42         ss << i;
43         ss >> s;
44         if(is_valid(s)){
45             permutation[count] = s;
46             count++;
47         }
48     }
49 }
50 bool is_valid(string s){
51     //Post:return true if s can represent a permutation of ABCDE.
52     bool used[5];
53     memset(used,false,sizeof(used));
54     for(int i = 0;i < 5;i++){
55         if(s[i] - '0' > 5 || s[i] == '0')
56             return false;
57         if(used[s[i] - '0' - 1] == true)//duplicated
58             return false;
59         used[s[i] - '0' - 1] = true;
60     }
61     return true;
62 }
63 int get_value(string *rankings,int i,int n){
64     int result = 0;
65     for(int j = 0;j < n;j++){
66         result += get_a_value(rankings[j],permutation[i]);
67     }
68     return result;
69 }
70 int get_a_value(string s1,string s2){
71     int positions1[5],positions2[5],result = 0;
72     for(int i = 0;i < 5;i++){
73         positions1[s1[i] - 'A'] = i + 1;
74         positions2[s2[i] - '1'] = i + 1;
75     }
76     for(int i = 0;i < 5;i++){
77         for(int j = i + 1;j < 5;j++){
78             if((positions1[i] - positions1[j]) * (positions2[i] - positions2[j]) < 0)
79                 result++;
80         }
81     }
82     return result;
83 }

Sicily 1006. Team Rankings 解题报告

相关推荐