2 shunfurh shunfurh 于 2017.09.06 21:45 提问

Team Rankings

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.

1个回答

caozhy
caozhy   Ds   Rxr 2017.09.22 08:17
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
Team Rankings
搜索#include <iostream> #include <cstring> using namespace std; char tmp[10]; char data[110][10]; int vis[10]; int ans = 2<<10; int n; char hh[10]; int findchar(char* s,char k) { for (int i=0;i<strle
[BZOJ1901][ZOJ2112]Dynamic Rankings-带修改的主席树-树状数组
Dynamic RankingsDescriptionThe Company Dynamic Rankings has developed a new kind of computer that is no longer satisfied with the query like to simply find the k-th smallest number of the given N numbe
Bzoj 1901 Zju2112 Dynamic Rankings(树状数组+主席树)
转载请注明出处,谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents    by---cxlove 题目:给出一个序列,查询区间第K小,修改某个数 http://www.lydsy.com/JudgeOnline/problem.php?id=1901   对于每一个位置建立主席树,和静态主席树不一样。 由于 有修改操作,每一棵
1006. Team Rankings
转 http://blog.csdn.net/ederick/article/details/7226807 和http://www.w3c.com.cn/sicily-1006-team-rankings 这题虽然大概懂意思,但还是不太懂那些数字怎么来的。找些感觉不错的代码先mark #include #include #include using namespace std;
sicily 1006 Team Rankings
在这题卡了很久,主要是没读懂题意,今天再去看题,突然就明白了。 关键是 median ranking的定义,其实这个定义跟逆序数一个意思。 接着是对于给出的voters的处理,这些是用来做一个源字符串的(词穷,不知道怎么叫更准确),用来确定给出的ranking有多少个逆序数。 因为一共有5!=120个ranking,所以需要一个个的算了。这里有一个偷懒的函数,c++的algorithm库中的全排列
Sicily 1006. Team Rankings
求逆序对数,数据规模小,暴力即可。 这里还用到了STL中的组合数函数next_permutation(),顺便贴上该函数的用法:http://www.cplusplus.com/reference/algorithm/next_permutation/ #include #include #include #include #include #include #include
ZOJ 2207 Team Rankings
枚举ABCDE排列即可,next_permutation好用. #include #include #include #include using namespace std; struct ranks{ int v[6]; char str[6]; }rks[101]; int n; int main(){ while (scanf("%d", &n) && n){ cha
soj.1006 Team Rankings
问题介绍:输入n个ABCDE的组合字符串,要求找出与这些组合的各字母组(如A和B的关系)的前后顺序差别最少的一个组合。 问题剖析:一开始我本来是不想用枚举看能不能做出来,但明显这题需要枚举,枚举的话使用stl的algorithm里的next_permutation函数就最方便不过。   而在判断字母组之间的差别,我利用string的成员函数find,通过两个字母的find值相减,然后对
[SOJ1006] Team Rankings
用枚举法实现 代码如下: //我是先用全排列生成了全部的串,再写的 全排列生成代码,点击可看 枚举的时候用了减枝,所以可能会稍微快点 但是emmm 看完师兄们的解法只需要0.00sec之后,我这个0.02sec的菜鸡就不知道该说什么好了代码如下:(会比较好理解)#include &lt;iostream&gt; #include &lt;vector&gt; using namespace std; #incl
sicily 1006 Team Rankings
01.// source code of submission 731830, Zhongshan University Online Judge System 02.#include 03.#include 04.#include 05.usingnamespacestd; 06.  07.intfind(charx,charstr[])                         //寻找字符在指定字符串中的位置 08.{ 09.    intindex; 10.    for(inti =