算法二十四：最后胜出队伍

ゝ一纸荒年。 2022-04-16 06:10 440阅读 0赞

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。

从order数组中，每次都选出两支队伍比赛，失败的队伍将退出比赛，所以我们可以用list来存储队伍，每经过一场比赛，将失败的队伍删除，持续这种过程知道最后只剩一支队伍，就是最后获胜的队伍。由于要输出最后比赛的名次，所以可以将每次失败的队伍取出来放到结果中。

\#include< stdio.h>

\#include< list>

\#include< iostream>

void raceResult(int\*\* w, int\* order, int\* result, int n)

\{

std::list<int> winer;

int count = n;

while(n)

\{

winer.push\_front(order\[--n\]);

\}

int resultNum = count - 1;

int nFirst, nSecond;

int round = 1;

while(winer.size()> 1)

\{

//一轮开始

std::cout<<std::endl<<"round "<<round++<<std::endl;

std::list<int>::iterator it = winer.begin();

while (it != winer.end())

\{

nFirst = \*it;

if (++it == winer.end())

\{

//轮空

std::cout<<nFirst<<" rest this round"<<std::endl;

\}

else

\{

nSecond = \*it;

int nWiner = \*((int\*)w + count \* nFirst + nSecond);

if (nWiner == nFirst)

\{

it = winer.erase(it);

result\[resultNum--\] = nSecond;

std::cout<<nFirst<<" kick out "<<nSecond<<std::endl;

\}

else

\{

it = winer.erase(--it);

result\[resultNum--\] = nFirst;

\++it;

std::cout<<nSecond<<" kick out "<<nFirst<<std::endl;

\}

\}

\}

\}

if (winer.size() == 1)

\{

result\[0\] = winer.front();

\}

std::cout<<std::endl<<"final result: ";

int nPlace = 0;

while(nPlace < count)

\{

std::cout<<std::endl<<result\[nPlace++\];

\}

\}

void test()

\{

//team 2>team 1>team 3>team 0>team 4>team 5

int w\[6\]\[6\] = \{

0,1,2,3,0,0,

1,1,2,1,1,1,

2,2,2,2,2,2,

3,1,2,3,3,3,

0,1,2,3,4,5

\};

int order\[6\] = \{1,3,4,2,0,5\};

int result\[6\] = \{-1\};

raceResult((int\*\*)w, order, result, 6);

getchar();

\}

发表评论取消回复

表情：

评论列表（有 0 条评论，440人围观）

还没有评论，来说两句吧...

相关阅读

相关 Qt第四十四章：弹出窗口

目录一、窗口一闪而逝二、弹出窗口三、多窗口弹出四、模态五、局部模态 -------------------- 一、窗口一闪而逝 impor

冷不防/ 2024年03月30日 11:02/ 0 赞/ 75 阅读

相关面试题(二十四)数据结构与算法

9.1哈希请谈一谈，hashCode() 和equals() 方法的重要性体现在什么地方？考察点：JAVA哈希表参考回答： Java中的HashMap

末蓝、/ 2024年03月27日 16:28/ 0 赞/ 100 阅读

相关数据结构与算法分析：（十四）二叉树

一、前言前面我们讲了都是线性表结构，比如：数组、链表、栈、队列等。今天我们终于可以讲一讲树了，`树`是`非线性结构`。我们都知道，对于大量的输入数据，链表的线性访问

骑猪看日落/ 2023年07月25日 08:56/ 0 赞/ 31 阅读

相关 [算法系列之二十四]后缀树（Suffix Tree）

之前有篇文章（\[算法系列之二十\]字典树（Trie））我们详细的介绍了字典树。有了这些基础我们就能更好的理解后缀树了。一引言模式匹配问题给定一个文本text\[0

柔情只为你懂/ 2023年06月19日 11:06/ 0 赞/ 19 阅读

相关二十四种模式

1，创建型模式一、抽象工厂模式(Abstract factory pattern): 提供一个接口, 用于创建相关或依赖对象的家族, 而不需要指定具体类. 二、生成器模式

￡神魔★判官ぃ/ 2022年08月27日 05:38/ 0 赞/ 199 阅读

相关数字图像处理领域的二十四个典型算法

转自：[http://blog.csdn.net/v\_JULY\_v/article/details/6210124][http_blog.csdn.net_v_JULY_v

逃离我推掉我的手/ 2022年08月07日 09:47/ 0 赞/ 196 阅读

相关算法十四：象棋

描述你有足够多的象棋“车”，在一个n×n的棋盘上你能放多少个“车”呢？注意，所给棋盘上有些位置不能放任何东西。同时，某一行（列）最多只能存在一个“车”。输入

小鱼儿/ 2022年05月23日 20:08/ 0 赞/ 212 阅读

相关算法二十四：矩形

描述给定两个矩阵，判断第二个矩阵在第一个矩阵的哪些位置出现过。输入输入的第一行包含四个正整数a,b,c,d，表示第一个矩阵大小为a×b，第二个矩阵的大小为c

分手后的思念是犯贱/ 2022年05月21日 08:10/ 0 赞/ 208 阅读

相关算法二十四：最后胜出队伍

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

ゝ一纸荒年。/ 2022年04月16日 06:10/ 0 赞/ 441 阅读

相关 053(二十四）

116、 116.Which two are the uses of the ASM metadata backup and restore (AMBR) featu

Dear 丶/ 2021年12月24日 01:43/ 0 赞/ 212 阅读