队列使用

一、队列概念

　　队列是一种先进先出的数据结构，与生活中常见的队列一样，具体可以参考严蔚敏版《数据结构》中关于队列的概述

二、题目

　　

 

 

 

 题目大意，给出NP只老鼠，按照NG个老鼠一组进行分组，第二行输入每只老鼠的质量，第三行输入这些老鼠的编号。

要求对NP只老鼠的重量进行排名，NG只一组进行小组赛，每个小组的第一出线进行下一轮比赛，下一轮中也是NG只老鼠为一组，分组时最后一组不满NG只也算作一组。直到最后只剩下一只老鼠出线。

要求返回的结果为每只老鼠的排名，在同一轮比赛中被淘汰的老鼠排名相同。

 

算法思路：首先定义一个mouse结构体，结构体中存放质量和排名；需要一个队列处理每轮比赛中晋级的老鼠。因为有排名相同的老鼠存在所以可能出现有两个第2名从而没有第三名的情况。所以排名group为每轮分组的个数加一，因为每组必有一个老鼠出现，那么group组有group只老鼠，这group只老鼠会占前group名。

 

代码：

 

 

 

 

 算法详细分析：因为队列的性质是先进先出，所以可以循环的使用这个队列，如输入案例，首先入队的是6、0、8这其实是mouse[]的下标，这三个元素比较后会保留weight大的mouse把下标入队，其他元素出队并给rank赋值，每次for（i<group）循环都会产生一个最大的weight并入队，所以队中元素在逐渐减少，到队里只剩下一个元素时，就是最后的冠军。在最后只需要按顺序输出mouse中rank的值就可以了。