/*36.引用自网友：longzuo（运算）谷歌笔试： 19n 支队伍比赛，分别编号为 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, 0, n * sizeof(int));    vector<int> stack;    int round = 0;    int n2 = n;    while(n2 != 1)    {        n2 = (n2>>1);        round++;    }    for(int r = 0; r < round; r++) //对比赛轮次循环    {        int i = 0;        int num = 0;        int member[2] = {0};        while(i < n)//对比赛队伍循环        {            if(result[i] == r)            {                member[num++] = i;            }            if(num == 2)            {                if(*((int*)w + n * member[0] + member[1]) == member[0])                {                    result[member[0]]++;                    stack.push_back(member[1]);                }                else                {                    result[member[1]]++;                    stack.push_back(member[0]);                }                num = 0;            }            i++;        }    }    for(int i = 0; i < n; i++) //冠军进栈    {        if(result[i] == round)        {            stack.push_back(i);        }    }    for(int i = 0; i < n; i++)    {        result[i] = stack.back();        stack.pop_back();    }}int main(){    int w[4][4] = {{0, 0, 2, 0},                   {0, 1, 1, 3},                   {2, 1, 2, 3},                   {0, 3, 3, 3}};    int order[4] ={1, 2, 3, 4};    int result[4];    getRank((int **)w, order, (int *)result, 4);    return 0;}

/*----------------------------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 > 0);    int i32I = 0, i32J = 0;    int nCurPos = nGroup - 1;    vector<int> vectOrder;    for (i32I = 0; i32I < nGroup; i32I++)        vectOrder.push_back(pOrder[i32I]);    while (vectOrder.size() > 1)    {        for (vector<int>::iterator it = vectOrder.begin(); it != vectOrder.end(); ++it)        {            if (it + 1 != vectOrder.end())            {                if (ppW[*it][*(it+1)] == *it)                {                    pResult[nCurPos--] = *(it+1);                    vectOrder.erase(it+1);                }                else                {                    pResult[nCurPos--] = *it;                    it = vectOrder.erase(it);                }            }        }    }    if (vectOrder.size() == 1)        pResult[nCurPos--] = vectOrder[0];    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 = 0; i32I < n; i32I++)    {        ppW[i32I] = new int [n];        assert(ppW);        for (int i32J = 0; i32J < n; i32J++)            cin >> ppW[i32I][i32J];    }    int *pOrder = new int[n];    assert(pOrder);    cout << "请输入出场顺序" << endl;    for (int i32I = 0; 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 = 0; i32I < n; i32I++)            cout << pRes[i32I] << " ";    }    //don‘t forget to free memory...    return 0;}

#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;}