学步园

/*
36.引用自网友：longzuo
谷歌笔试：
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<stdio.h>
using namespace std;

void knockOut(int w[][5],int order[],int result[],int n)
{
	int i=0,j=0;
	memcpy(result,order,n*sizeof(int));
	
	while(n>1)
	{
		i=0;j=0;
		for(;j<n/2;)
		{
			if(order[i]==w[order[i]][order[i+1]])
			{
				result[j]=order[i];
				result[n-1-j]=order[i+1];
			}
			else
			{
				result[j]=order[i+1];
				result[n-1-j]=order[i];
			}
			
			i+=2;j++;
		}
		if(n%2==1)//奇数 最后一个复制一遍 
		{
			result[j]=order[i];
			n++;
		}
		n/=2;// 把result的前n/2个（就是刚从胜出的） 赋值给order，继续排序 
		memcpy(order,result,n*sizeof(int));
	}
}

int main()
{
	int i;
	int order[]={2,3,0,1};   
	int w[][5] = {{0,0,2,3},
				   {0,1,2,3},
				   {2,2,2,2},
				   {3,3,2,3}
					};  
  	int result[5]={0};
  	
	knockOut(w,order,result,4);
	//比赛对阵2-3 0-1 ==> w[2][3]=2,w[0][1]=0==>w[2][0]=2;
	cout<<result[0]<<endl;   
	
	int w2[][5] = {  
        {0,1,0,3,0},  
        {1,1,2,3,1},  
        {0,2,2,2,4},  
        {3,3,2,3,3},  
        {0,1,4,3,4}  
    };  
    int order2[5] = {0,1,2,3,4};
    int result2[5]={0};
	knockOut(w2,order2,result2,5);
	//比赛对阵0-1 2-3 4-4 ==> w[0][1]=w[1][0]=1,w[2][3]=2 ,4 => 1-2 4-4 
						 //  =>w[1][2]=2-4=>w[2][4]=4
	cout<<result2[0]<<endl; 
	return 0;
}