编程介的小学生 2017-09-06 13:45 采纳率: 20.5%
浏览 673
已采纳

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条回答

  • threenewbee 2017-09-22 00:17
    关注

    http://blog.csdn.net/tsinting/article/details/53310064

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题？

  • Team Rankings
    2017-03-26 07:36
    回答 2 已采纳 http://blog.csdn.net/stloztoeplitz/article/details/54411915
  • 这个正则表达式的负面断言是什么？ php
    2013-02-04 09:46
    回答 2 已采纳 Do not use regex to parse HTML, use PHP Domdocument instead.
  • ICPC Scoreboard
    2017-12-02 16:47
    回答 1 已采纳 http://www.acmerblog.com/hdu-1940-ICPC-Scoreboard-3015/
  • sicily 1006. Team Rankings
    2015-11-16 13:52
    奈伊夫的博客 1006. Team Rankings 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
  • Programmer, Rank Thyself
    2017-01-24 14:58
    回答 1 已采纳 http://blog.csdn.net/csuhoward/article/details/16844701
  • Contest Scoreboard
    2017-09-09 04:45
    回答 2 已采纳 http://blog.csdn.net/killua_hzl/article/details/2213800
  • soj.1006 Team Rankings
    2015-09-20 16:51
    qq_26814841的博客 问题介绍：输入n个ABCDE的组合字符串，要求找出与这些组合的各字母组（如A和B的关系）的前后顺序差别最少的一个组合。 问题剖析：一开始我本来是不想用枚举看能不能做出来，但明显这题需要枚举，枚举的话使用...
  • Team Rankings
    2017-01-13 20:52
    stloztoeplitz的博客 搜索#include #include using namespace std; char tmp[10]; char data[110][10]; int vis[10]; int ans = 2; int n; char hh[10]; int findchar(char* s,char k) { for (int i=0;i<strle
  • 1006. Team Rankings
    2019-10-04 02:24
    aa662665的博客 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 ...
  • POJ 2038 Team Rankings G++
    2020-05-18 18:38
    woniupengpeng的博客 #include <iostream> #include <string> #include <algorithm> #include <cstdio> using namespace std; //英语 抄博友程序 next_permutation string a[108]; int main() ......
  • 『杭电1310』Team Rankings
    2020-07-11 09:50
    漠宸离若的博客 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...
  • HDU 1310（Team Rankings）
    2020-03-17 17:30
    Intelligence1028的博客 本题的核心是求字符串的全排列，头文件 中包含库函数 next_permutation，用来按字典序求下一个排列。 依次求出每个排列与给定所有... } } while (next_permutation(team, team + 5)); cout ; } return 0; } 继续加油。
  • 算法学习【10】—— 1006. Team Rankings
    2012-04-13 20:45
    BetaBin的博客 题目来源：... 1006. Team Rankings Description It's preseason and the local newspaper wants to publish a preseason ranking of the teams in the local amateur basketball league
  • poj 2038 Team Rankings 枚举排列
    2019-10-01 06:36
    aofan9566的博客 //poj 2038 //sep9 #include <iostream> #include <algorithm> using namespace std; char s[128][8]; int count(char s1[],char s2[]) { int cnt=0; for(int i=0;... for(int j=i...
  • ZOJ - 2207 Team Rankings（待ac）
    2015-07-25 20:05
    acm_1361677193的博客 这个题主要是代码写起来麻烦，dfs。 等状态好了再独立写出。 http://blog.csdn.net/zxy_snow/article/details/6131852 http://blog.csdn.net/zxjcarrot/article/details/8942210
  • Sicily.1006. Team Rankings
    2012-12-26 11:47
    豪运SYSU的博客 Team Rankings题目大意：给出n串由A B C D E组成的任意字符序列，求出与这n串序列 之间的差值最小的序列，并输出其差值. 求两串字符的差值规则：如 ABDCE, BACDE, ABCED and ACBDE， 则ABCDE 与他们的差值和为1 + ...
  • Sicily 1006 Team Rankings
    2014-10-19 22:44
    骗神南宫煌的博客 1006. Team Rankings 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 ...
  • [sicily online]1006. Team Rankings
    2012-11-28 16:55
    qiuchenl的博客 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 ...
  • [SOJ1006] Team Rankings
    2017-10-19 14:59
    肥宅_Sean的博客 用枚举法实现 代码如下： //我是先用全排列生成了全部的串，再写的 ...枚举的时候用了减枝，所以可能会稍微快点 但是emmm 看完师兄们的解法只需要0.00sec之后，我这个0.02sec的菜鸡就不知道该说什么好了代码如下:...
  • 没有解决我的问题, 去提问

悬赏问题

  • ¥15 优质github账号直接兑换rmb，感兴趣伙伴可以私信
  • ¥15 错误(10048): “调用exui内部功能”库命令的参数“参数4”不能接受空数据。怎么解决啊
  • ¥15 安装svn网络有问题怎么办
  • ¥15 Python爬取指定微博话题下的内容，保存为txt
  • ¥15 vue2登录调用后端接口如何实现
  • ¥65 永磁型步进电机PID算法
  • ¥15 sqlite 附加（attach database）加密数据库时，返回26是什么原因呢？
  • ¥88 找成都本地经验丰富懂小程序开发的技术大咖
  • ¥15 如何处理复杂数据表格的除法运算
  • ¥15 如何用stc8h1k08的片子做485数据透传的功能？(关键词-串口)