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

http://blog.csdn.net/yuucyf/article/details/6733226

题目：

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。

 

思路一：

题目说明很多，但是其实具体做法还是蛮简单的，其实最主要的是用来存储实力的二维数组的创建，从这个二维数组中已经可以确定实力最好的队伍，然后根据出场顺序再确定具体排名。主要看的懂题目就会明白它的做法，不用在多说了，具体看代码.

 

代码如下：

/*----------------------------
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;
}