共计 5081 个字符，预计需要花费 13 分钟才能阅读完成。
题目粗心:
给出 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;
}
正文完
