求比赛排名

n支队伍比赛,分别编号为0,1,2。。。。n-1,已知它们之间的实力对比关系,
存储在一个二维数组w[n][n]中,w[i][j] 的值代表编号为i,j的队伍中更强的一支。

所以w[i][j]=i 或者j,现在给出它们的出场顺序,并存储在数组order[n]中,
比如order[n] = {4,3,5,8,1……},那么第一轮比赛就是 4对3, 5对8。…….

胜者晋级,败者淘汰,同一轮淘汰的所有队伍排名不再细分,即可以随便排,
下一轮由上一轮的胜者按照顺序,再依次两两比,比如可能是4对5,直至出现第一名

编程实现,给出二维数组w,一维数组order 和 用于输出比赛名次的数组result[n],求出result。

思路:

常见的思路肯定是模拟。

用一个临时数组保存本轮winner胜利的人,loser存到result中,倒着存。

特别注意w比较的是w[tmp[i][[tmp[i+1]]而不是w[i][i+1]。

另外一定要先存loser,再改tmp,否则。。你懂的。

思路2:

是的,模拟没有错。其实这是一道传说中Google的笔试题,肯定不会这么简单。

网上有人说,这题有个Bug,其实主要取决于给的数据吧。即对于w[i][x],我们只要知道w可赢几个人就OK了,无序关注比赛顺序。这个我实践过,是错误的。因为实例只是i和j之间,不存在传递(全序)关系。

思路3:

其实思路1的代码可以去掉哪个tmp数组,直接在result(从order拷贝)上swap,不过代码比较复杂,还没写出来。

 

Leave a Reply

Your email address will not be published.