36.引用自网友：longzuo（运算）
谷歌笔试：
19
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。
我用result先存储每个队伍晋级的轮次，利用vector后进先出的特点来输出结果
/*
36.引用自网友：longzuo（运算）
谷歌笔试：
19
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。
*/
#include <iostream>
#include <vector>
#include <string.h>
using namespace std; //假设n一定是2的n次方，即每一轮不会出现轮空的情况
void getRank(int *w[], int * order, int * result, int n)
{
memset(result, , n * sizeof(int));
vector<int> stack;
int round = ;
int n2 = n;
while(n2 != )
{
n2 = (n2>>);
round++;
}
for(int r = ; r < round; r++) //对比赛轮次循环
{
int i = ;
int num = ;
int member[] = {};
while(i < n)//对比赛队伍循环
{
if(result[i] == r)
{
member[num++] = i;
}
if(num == )
{
if(*((int*)w + n * member[] + member[]) == member[])
{
result[member[]]++;
stack.push_back(member[]);
}
else
{
result[member[]]++;
stack.push_back(member[]);
}
num = ;
}
i++;
}
} for(int i = ; i < n; i++) //冠军进栈
{
if(result[i] == round)
{
stack.push_back(i);
}
} for(int i = ; i < n; i++)
{
result[i] = stack.back();
stack.pop_back();
}
} int main()
{
int w[][] = {{, , , },
{, , , },
{, , , },
{, , , }};
int order[] ={, , , };
int result[];
getRank((int **)w, order, (int *)result, );
return ;
}
我的实现不好，因为没有考虑轮空的情况。网上有两个我觉得还不错的方法，都考虑了轮空，也很简洁。
http://blog.csdn.net/yuucyf/article/details/6733226
利用了vector 的 earse 每次存名次的时候从 result的最后一个开始存就可以了。
/*----------------------------
Copyright by yuucyf. 2011.08.30
-----------------------------*/
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <assert.h>
using namespace std; bool CalcPosition(int **ppW, int *pOrder, int *pResult, int nGroup) //nGroup arg mean n x n
{
assert(ppW);
assert(pOrder);
assert(pResult);
assert(nGroup > ); int i32I = , i32J = ;
int nCurPos = nGroup - ;
vector<int> vectOrder;
for (i32I = ; i32I < nGroup; i32I++)
vectOrder.push_back(pOrder[i32I]); while (vectOrder.size() > )
{
for (vector<int>::iterator it = vectOrder.begin(); it != vectOrder.end(); ++it)
{
if (it + != vectOrder.end())
{
if (ppW[*it][*(it+)] == *it)
{
pResult[nCurPos--] = *(it+);
vectOrder.erase(it+);
}
else
{
pResult[nCurPos--] = *it;
it = vectOrder.erase(it);
}
}
}
} if (vectOrder.size() == )
pResult[nCurPos--] = vectOrder[]; return true;
} int _tmain(int argc, _TCHAR* argv[])
{
int n;
cout << "请输入队伍数";
cin >> n;
cout << endl << "输入实力对比关系" << endl; int **ppW = new int* [n];
assert(*ppW);
for (int i32I = ; i32I < n; i32I++)
{
ppW[i32I] = new int [n];
assert(ppW);
for (int i32J = ; i32J < n; i32J++)
cin >> ppW[i32I][i32J];
} int *pOrder = new int[n];
assert(pOrder);
cout << "请输入出场顺序" << endl;
for (int i32I = ; i32I < n; i32I++)
cin >> pOrder[i32I]; int *pRes = new int[n];
assert(pRes);
if (CalcPosition(ppW, pOrder, pRes, n))
{
cout << endl << "比赛名次为:(大到小)" << endl;
for (int i32I = ; i32I < n; i32I++)
cout << pRes[i32I] << " ";
} //don't forget to free memory... return ;
}
http://www.tuicool.com/articles/jq2INv
用变量i k的跳跃实现每一轮的队伍选取。 二维指针传参的地方可以改进。
#include<iostream> using namespace std; #define N 5
void GetResult(int (*w)[N], int* order, int* result)
{
int i = ;
int k = ;
int j = N -;
while()
{
i = ;
if(i + k > N -)
{
result[j] = order[];
break;
} while(i + k <= N-)
{
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 + *k;
}
k *= ;
}
} int main()
{
int a[][] = {{,,,,},{,,,,},{,,,,},{,,,,},{,,,,}};
int order[] = {,,,,};
int result[];
GetResult(a, order, result); int i = ;
cout << "result order: ";
while(i < )
{
cout << result[i++] << ",";
}
cout << endl;
}