谷歌面试题解析：n支队伍比赛，分别编号为0，1，2。。。。n-1

谷歌面试题解析：n支队伍比赛，分别编号为0，1，2。。。。n-12014-12-24题目：

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。

分析：

这题不难，只需要不断地遍历order表，直到找到所有对比结果。

实现如下：

#include<iostream>using namespace std;#define N 5void GetResult（int （*w）[N], int* order, int* result）{int i = 0;int k = 1;int j = N -1;while（1）{i = 0;if（i + k > N -1）{result[j] = order[0];break;}while（i + k <= N-1）{int ii = order[i];int jj = order[i+k];if（w[ii][jj] == ii）result[j--] = jj;else{result[j] = ii;order[i]= order[i+k];order[i+k] = result[j];j --;}i = i + 2*k;}k *= 2;}}int main（）{int a[5][5] = {{0,1,2,3,4},{1,1,2,3,4},{2,2,2,3,4},{3,3,3,3,4},{4,4,4,4,4}};int order[5] = {4,3,1,2,0};int result[5];GetResult（a, order, result）;int i = 0;cout << "result order: ";while（i < 5）{cout << result[i++] << ",";}cout << endl;}

输出结果为：

result order: 4,0,2,1,3,

作者：csdn博客 hhh3h