题目粗心:
给出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;
}
发表回复