题目粗心:
给出NP只老鼠的品质,并且给出它们较量的程序,而后每NG只老鼠为一组,最初不够NG只的也为一组,而后组内比赛,体重最大的胜出进入下一轮较量,本轮较量输掉的排名均一样,要求输入依照编号从小到大输入最初的排名,这里得留神下题目的意思,也就是第3行给的数据,这个实际上是老鼠的下标,而后输入的程序是依照0到NP-1的程序
算法思路：
示例解读：
首先得明确一点，在给定初始参赛人数和每组人数的状况下，能够明确晓得具体较量的次数(轮次)和每一次较量结束后，失败者的名次。
对于具体较量的次数的获取如下代码：
int round = 1;//总轮次// 计算出总轮次while(NP!=1){ if(NP%NG==0){ NP = NP/NG; }else { NP = NP/NG + 1; } ++round;}每一场较量失败者的名次的获取如下代码：
int round = 1;//总轮次// 计算出总轮次和每一次较量失败者的名次 while(NP!=1){ if(NP%NG==0){ NP = NP/NG;// 以后round轮较量有NP集体胜出,表明以后轮的loser后面有NP集体，他们的排名都是NP+1 }else { NP = NP/NG + 1; } rankByRound[round] = NP+1; ++round;}rankByRound[round] = 1;// 记录最初一轮的名次这里应用了round记录总的较量次数，rankByRound数组记录了每一轮较量失败者的名次。而后咱们将每一场较量的参赛人数应用一个队列保留，queue<int> q[currentRound]保留的就是以后轮次较量的参赛人数，而后接着就是模仿较量的过程，咱们应用popNum记录以后轮次曾经加入了较量的人数，size记录以后轮次总的较量人数，如果size==1阐明只有一个人，间接赋值排名即可，否则，只有popNum<size阐明以后的较量还未完结，就让needPop记录以后较量小队的人数，而后在needPop的人中选择权值最大的人作为winner，退出下一轮的较量中q[currentRound+1].push(winner); 。所有的失败者都会被赋予排名并且从新回到以后队列(rank[loser] = rankByRound[currentRound];q[currentRound].push(loser))。记得更新popNum和currentRound，最初输入排名即可。
留神点：
1、当队列中只有一个人的时候须要特判，间接退出循环即可。
2、如果测试点5运行超时，能够思考更改获取排名的形式，具体见AC代码1。如果不想扭转获取排名的形式，能够参考AC代码2。
提交后果：
这里给出2种不同的实现形式，次要差别在于获取排名的形式上，AC代码1应用了先计算出所有轮次的排名，在每一轮较量中，对失败者赋值排名。AC代码2而是最初遍历每一个队列进行的排名赋值操作。AC代码1应用遍历队列残余元素获取排名会导致最初一个测试点超时。
AC代码1：
#include<cstdio>#include<queue>using namespace std;queue<int> q[15];// 每一轮较量都应用一个队列来存储int main(){ int NP,NG;//程序员人数和最多NG只老鼠组成一组 scanf("%d %d",&NP,&NG); int weight[NP];// 每一只老鼠的权值 int rank[NP];// 每一只老鼠的最终排名 int rankByRound[NP];// 每一轮失败者的名次 for(int i=0;i<NP;++i){ scanf("%d",&weight[i]); } int currentRound = 1;//以后较量的轮次 // 初始化较量对象 int order; for(int i=0;i<NP;++i){ scanf("%d",&order); q[currentRound].push(order); } int n = NP; int round = 1;//总轮次 // 计算出总轮次和每一次较量失败者的名次 while(NP!=1){ if(NP%NG==0){ NP = NP/NG;// 以后round轮较量有NP集体胜出,表明以后轮的loser后面有NP集体，他们的排名都是NP+1 }else { NP = NP/NG + 1; } rankByRound[round] = NP+1; ++round; } rankByRound[round] = 1;// 记录最初一轮的名次 // 较量开始 while(currentRound<=round){ int popNum = 0;//曾经出队的人数 int size = q[currentRound].size();//以后轮较量参赛人数 if(size==1){ // 以后轮为最初一轮，无需较量，间接赋值排名即可 rank[q[currentRound].front()] = rankByRound[currentRound]; break; } while(popNum<size){ int needPop = size-popNum>=NG?NG:size-popNum;//须要出队人数 int winner = q[currentRound].front();//首先保留队首元素为赢家 q[currentRound].pop(); ++popNum; for(int i=0;i<needPop-1;++i){ // 在残余的needPop-1个较量人员中获取权值最大的那个 if(weight[winner]<weight[q[currentRound].front()]){ // 队首元素胜,首先将winner退出队列，而后更新winner rank[winner] = rankByRound[currentRound];// 给loser赋值以后排名 q[currentRound].push(winner); winner = q[currentRound].front(); q[currentRound].pop(); } else { // 队首元素败,将队首元素增加至开端 int loser = q[currentRound].front(); rank[loser] = rankByRound[currentRound];// 给loser赋值以后排名 q[currentRound].pop(); q[currentRound].push(loser); } ++popNum; } // 将赢家退出下一轮的较量中 q[currentRound+1].push(winner); } ++currentRound; } // 输入排名 for(int i=0;i<n;++i){ printf("%d",rank[i]); if(i<n-1) printf(" "); } return 0;} AC代码2：
#include<cstdio>#include<queue>#include<vector>using namespace std;/*题目要求: 给出NP只老鼠的品质,并且给出它们较量的程序,而后每NG只老鼠为一组,最初不够NG只的也为一组,而后组内比赛,体重最大的胜出进入下一轮较量,本轮较量输掉的排名均一样,要求输入依照编号从小到大输入最初的排名,这里得留神下题目的意思,也就是第3行给的数据,这个实际上是老鼠的下标,而后输入的程序是依照0到NP-1的程序 算法思路:这里放上本人的手稿,不便了解,就是个模仿的题目(最烦这种的了)第一轮(0): 6 0 (8)(第一组,8获胜) ,(7) 10 5(第二组,7获胜),(9) 1 4(第三组,9获胜),2 (3)(第4组,3获胜)第二轮(1): (8) 7 9(第一组,8获胜),(3)(第二组,就一个,3获胜)第三轮(2): (8) 3(第一组,8获胜)第四轮(3): (8)(第一组,只有一个较量完结)1.数据的存储:应用w,order数组存储每只老鼠的数量和较量的初始程序,rank数组记录最初的每只老鼠的排名,queue<int> v[1000]保留每一轮的失败者,最初一轮是胜利者turn记录以后较量的轮次,初始为0(和下面第几轮前面括号雷同) 2.最开始的较量程序全副保留在v[0]中,而后对每一轮较量进行模仿,咱们应用count记录每一轮的参赛残余老鼠数目,起因是咱们将会把较量输掉的老鼠从新入队,避免出队谬误,那么只有count!=0就阐明以后轮较量还没完结,应用vector<int> a暂存以后队伍的老鼠的下标,目标是为了求得以后最大体重的老鼠的下标,而后只有count>=ng就出队ng只老鼠进a中,否则就出队count只老鼠(切记不能以队列为空为判断条件,因为之前队伍较量完后输掉的老鼠从新入队了),而后遍历a数组求得最大体重老鼠的体重maxW,最初从新再遍历a,只有以后老鼠的体重不等于maxW,阐明是失败者,就从新进入以后v[turn]队列,否则就进入下一轮较量v[turn+1],在以后轮较量结束后,++turn进入下一轮较量,并且在以后轮参赛老鼠个数为1的时候退出循环(因为没有老鼠可比拟了,阐明是最初的胜者)3.排名的获取:遍历v数组,不过得从以后最初的一轮较量往前遍历,因为最初胜出的才是第一名,当i==turn时,阐明是第一名,则rank[v[i].front()] = 1;否则以后轮所有老鼠的排名均为后面老鼠数量num+1(num初始为0),而后更新下一轮老鼠后面的个数num+=v[i].size()4.最初依照程序输入rank即可一点疑难:vector<queue<int> > v无奈应用,而queue<int> v[1000]却能够不晓得为什么,求指导 */queue<int> v[1000];//保留每一轮的失败者,最初一轮是胜利者 int turn = 0;//以后较量的轮次 int main(){ int np,ng;//总老鼠数和每队老鼠数 scanf("%d %d",&np,&ng); int w[np],order[np];//每只老鼠的分量,较量的程序 int rank[np];//最终的排名 int count;//每一轮的参赛残余老鼠数目 for(int i=0;i<np;++i){ scanf("%d",&w[i]); } for(int i=0;i<np;++i){ scanf("%d",&order[i]); v[turn].push(order[i]);//将第一轮较量程序增加进队列中 } while(true){ count = v[turn].size();//count初始为以后轮所有老鼠 if(count==1){//以后轮较量只有一只老鼠阐明较量完结 break; } while(count!=0){//同一轮次 vector<int> a;//暂存以后队伍的老鼠的下标 if(count>=ng){//残余的老鼠数目大于等于ng,就出队ng个老鼠 for(int i=0;i<ng;++i){ a.push_back(v[turn].front());//将以后队伍老鼠退出a中 v[turn].pop(); } count -= ng;//更新count }else{//残余老鼠个数不够ng个,所有残余count只老鼠为一对 while(count!=0){ a.push_back(v[turn].front()); v[turn].pop(); --count; } } int maxW=-1;//以后队伍最重的老鼠的体重 int len = a.size();//以后队伍人数 for(int i=0;i<len;++i){//找到以后队伍中最重的老鼠 if(w[a[i]]>maxW){ maxW = w[a[i]]; } } for(int i=0;i<len;++i){ if(w[a[i]]!=maxW){//失败者进入留在以后轮 v[turn].push(a[i]); }else{//胜利者进入下一轮 v[turn+1].push(a[i]); } } } ++turn;//进入下一轮较量 } int num = 0;//记录以后轮后面有多少只老鼠 for(int i=turn;i>=0;--i){ int len = v[i].size(); for(int j=0;j<len;++j){//第i轮队列残余的人的排名均雷同 rank[v[i].front()] = num+1; v[i].pop(); } num += len;//更新为下一轮老鼠后面有多少只老鼠 } for(int i=0;i<np;++i){ printf("%d",rank[i]); if(i<np-1) printf(" "); } return 0;}