求比赛名次 【微软面试100题 第三十六题】 - tractorman - 博客园

求比赛名次 【微软面试100题 第三十六题】 - tractorman - 博客园
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.
题目分析：
　　假设出场次序为：1 3 4 2 0 5,实力图和过程讲解如下图：

http://www.coder4.com/archives/3385

常见的思路肯定是模拟。

用一个临时数组保存本轮winner胜利的人，loser存到result中，倒着存。

特别注意w比较的是w[tmp[i][[tmp[i+1]]而不是w[i][i+1]。

另外一定要先存loser，再改tmp，否则。。你懂的。

void match(int w[MAX][MAX], int* order, int* result, int n)

{

    int tb = n;

    int tmp[MAX];

    int lose = n-1;

    int win = 0;

    int i;

    memcpy(tmp, order, sizeof(int)*n);

    while(tb>1)

    {

        win = 0;

        for(i=0;i<tb && (i+1)<tb;i+=2)

        {

            if(w[tmp[i]][tmp[i+1]]==tmp[i])

            {

                result[lose--] = tmp[i+1];

                tmp[win++] = tmp[i];

            }else

            {

                result[lose--] = tmp[i];

                tmp[win++] = tmp[i+1];

            }

        }

        if(tb%2==1)

        {

            tmp[win++] = tmp[tb-1];

        }

        tb = win;

        for(i=0;i<tb;i++)

        {

            printf("%d ", tmp[i]);

        }

        printf("\n");

    }

    result[0] = tmp[0];

}

void Calc(int ppW[][N],int *pOrder,int *pResult,int n)
{
    if(ppW==NULL || *ppW==NULL || pOrder==NULL || pResult==NULL || n<=0)
        return ;

    int nCurPos = n-1;
    vector<int> vectOrder;

    for(int i = 0;i<n;i++)
        vectOrder.push_back(pOrder[i]);

    while(vectOrder.size()>1)
    {
        for(vector<int>::iterator j = vectOrder.begin();j!=vectOrder.end();j++)
        {
            if(j+1 != vectOrder.end())
            {
                if(ppW[*j][*(j+1)] == *j)
                {
                    pResult[nCurPos--] = *(j+1);
                    vectOrder.erase(j+1);
                }
                else
                {
                    pResult[nCurPos--] = *j;
                    //这句话的意思就是删除j，返回值是j的后一位，把该位重新赋值给j
                    j = vectOrder.erase(j);
                }
            }
        }
    }
    if(vectOrder.size()==1)
        pResult[nCurPos--] = *(vectOrder.begin());
}

xfinitytv.comcast.net

（1）        建立order的一头一尾两个指针,i，j。

（2）        头尾指针每次移动两位，移动后指向的队伍需要跟下一个队伍比赛。也就是order[i]和order[i+1]比赛; order[j]和order[j-1]比赛。然后将尾指针两队中的获胜者跟头指针中两队的失败者互换。即是：loser[order[i]]win[order[i+1]] 与win[order[j]]win[order[j+1]]。

在这里根据参加比赛的队伍总数n的不同需要讨论几种特殊情况：

a)．n是4的倍数。停止条件为：i>j

i   i+1                         i   i+1  j-1  j                         j-1  j

b). n是偶数但不是4的倍数。停止条件为i>j

                i  j=i+1

c). n是奇数字。那么最初的尾指针为j=n-1，也就是把最后一支队轮空。

最后要把最后一个元素再换到前面去（黑色），因为它轮空了。

（3）        前i个元素再次进行相似的运算。直到n=1；

（4）        注意当j=i+1的时候需要保证胜利的队在序列的前面。

（5）        注意当数组元素为3的时候，i指向的元素跟轮空的元素（第三个元素）是相等的。而我们期望的是失败的元素（第二个元素）跟第三个元素进行互换。这种情况比较特殊，当且仅当只剩下3个元素的时候才会发生，所以需要用一段程序进行一定的修改。

Read full article from 求比赛名次 【微软面试100题 第三十六题】 - tractorman - 博客园