33

问答题 33 /104

现在有 n=2^k(k为正整数)支足球队,编号为0,1,...,n-1,给出二维数组winner[][],winner[i][j]表示当编号为i的队和编号为j的队比赛时,会胜出的队伍的编号,winner[i][j]一定是i,j之中的一个(不存在平局),输入保证winner[i][j]=winner[j][i],现在给出一个单败淘汰赛的签位一位数组order[],order[i]表示第i个签位上的队伍的编号,order保证是0到n-1的一个排列。返回比赛最后的排名顺序,同一轮被淘汰的队伍名次并列,并列的队伍之间的排名顺序任意。要求时间和空间复杂度尽量低。
将结果写到一维数组result[]里面即可。 接口定义:
c:
void calculate_result(int n, int **winner, int *order, int *result);
c++:
void calculate_result(int n, vectorwinner, vectororder, vectorresult);
Java:
void calculate_result(int n, int [][]winner, int []order, int []result);

参考答案

例子:
n=4, winner={{0,1,2,3},{1,1,2,1},{2,2,2,3},{3,1,3,3}} order={0,1,2,3} 第一轮0和1比赛,1胜出,2和3比赛,3胜出,第二轮1和3比赛,1胜出。 所以排名是1,3,0,2,0和2都是第一轮被淘汰,名词并列,互相之间顺序无所谓。
1<=n<=1000