題目
Constraints
Time Limit: 1 secs, Memory Limit: 32 MB
Description
It's preseason and the local newspaper wants to publish a preseason ranking of the teams in the local amateur basketball league. The teams are the Ants, the Buckets, the Cats, the Dribblers, and the Elephants. When Scoop McGee, sports editor of the paper, gets the rankings from the selected local experts down at the hardware store, he's dismayed to find that there doesn't appear to be total agreement and so he's wondering what ranking to publish that would most accurately reflect the rankings he got from the experts. He’s found that finding the median ranking from among all possible rankings is one way to go.
The median ranking is computed as follows: Given any two rankings, for instance ACDBE and ABCDE, the distance between the two rankings is defined as the total number of pairs of teams that are given different relative orderings. In our example, the pair B, C is given a different ordering by the two rankings. (The first ranking has C above B while the second ranking has the opposite.) The only other pair that the two rankings disagree on is B, D; thus, the distance between these two rankings is 2. The median ranking of a set of rankings is that ranking whose sum of distances to all the given rankings is minimal. (Note we could have more than one median ranking.) The median ranking may or may not be one of the given rankings.
Suppose there are 4 voters that have given the rankings: ABDCE, BACDE, ABCED and ACBDE. Consider two candidate median rankings ABCDE and CDEAB. The sum of distances from the ranking ABCDE to the four voted rankings is 1 + 1 + 1 + 1 = 4. We'll call this sum the value of the ranking ABCDE. The value of the ranking CDEAB is 7 + 7 + 7 + 5 = 26.
It turns out that ABCDE is in fact the median ranking with a value of 4.
Input
There will be multiple input sets. Input for each set is a positive integer n on a line by itself, followed by n lines (n no more than 100), each containing a permutation of the letters A, B, C, D and E, left-justified with no spaces. The final input set is followed by a line containing a 0, indicating end of input.
Output
Output for each input set should be one line of the form:
ranking is the median ranking with value value.
Of course ranking should be replaced by the correct ranking and value with the correct value. If there is more than one median ranking, you should output the one which comes first alphabetically.
Sample Input
4
ABDCE
BACDE
ABCED
ACBDE
0
Sample Output
ABCDE is the median ranking with value 4.
題目大意
有ABCDE五個(gè)隊(duì)伍，報(bào)紙編輯得到了一些人的投票馍乙，求出在這五隊(duì)伍的全排列中，和投票結(jié)果距離最小的排列吊输。
距離定義如下： 候選排列中和某一個(gè)投票的ranking不同的隊(duì)伍的對(duì)的個(gè)數(shù)铁追。
如候選排列ABCDE 和投票ABDCE 的距離為1.
思路
- 采用
<algorithm>里面的next_permutation函數(shù)獲取全排列； -
距離可以通過(guò)五個(gè)組位置之間的對(duì)比來(lái)確定琅束。
代碼
// Copyright (c) 2015 HuangJunjie@SYSU(SNO:13331087). All Rights Reserved.
// sicily 1006: http://soj.sysu.edu.cn/1006
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
// traverse all posible permutation and get the median ranking.
// @Param ranking: the array storing the votes.
// @Param num: the number of the votes.
// @return: a median ranking and its distance to votes.
pair<string, int> getMedian(string ranking[100 + 1], int num);
// a distance is defined as the number of different pairs' order of teams
// between string A and B.
// @Param A, B: the string to compare
int getDistance(string A, string B);
int main() {
int n; // number of strings.
string ranking[100 + 1]; // the votes from expert
while (cin >> n && n) {
// input a testcase of votes
for (int i = 0; i < n; i++) cin >> ranking[i];
// get the medien ranking
pair<string, int> median = getMedian(ranking, n);
// output a result.
cout << median.first << " is the median ranking with value " << median.second << "." << endl;
}
return 0;
}
pair<string, int> getMedian(string ranking[100 + 1], int num) {
// since the max distance is 10 and the number of string is no more than
// 100, 1000 as the max distance is enough.
int result = 1000 + 5, sum;
string str = "ABCDE", median;
do {
sum = 0;
for (int i = 0; i < num; i++) sum += getDistance(str, ranking[i]);
if (sum < result) {
result = sum;
median = str;
}
} while (next_permutation(str.begin(), str.end()));
return pair<string, int>(median, result);
}
int getDistance(string A, string B) {
int pos[5], distance = 0;
for (int i = 0; i < A.size(); i++) pos[A[i]-'A'] = i;
for (int i = 0; i < B.size(); i++) {
for (int j = i + 1; j < B.size(); j++) {
if (pos[B[i] - 'A'] > pos[B[j] - 'A']) distance++;
}
}
return distance;
}
參考
http://blog.csdn.net/jcjc918/article/details/9897703
http://blog.csdn.net/dijason/article/details/8147159
