PAT_甲级_1056 Mice and Rice

题目大意:

给出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;
}