【1056】Mice and Rice (25 分)

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>  
#include<map>
#include<vector>
#include<queue> 
using namespace std;  
//key:分组，每组最肥者进队成新组,按排名输出
//注意每次该轮未晋级的老鼠排名都为group+1
const int maxn=1010;
struct mouse{  //老鼠
  int weight; //质量
  int R;   //排名
}mouse[maxn];
int main(){   
  int np,ng,order;
  scanf("%d%d",&np,&ng);  //老鼠个数   每组要求个数
  for(int i=0;i<np;i++){  
    scanf("%d",&mouse[i].weight);
  }
  queue<int>q;   //定义一个队列
  for(int i=0;i<np;i++){   
    scanf("%d",&order);//题目给出的顺序
    q.push(order);   //按顺序把老鼠们的标号入队
  }
  int temp=np,group;   //temp为当前轮的比赛总老鼠数,group为组数
  while(q.size() != 1){
    //计算group，即当前轮分为几组进行比赛
    if(temp % ng==0)  group=temp/ng;
    else group =temp /ng +1;
    //枚举每一组，选出该组老鼠中质量最大的
    for(int i=0;i<group;i++){ 
      int k=q.front();  //k存放该组最大的老鼠的编号
      //下面这个for为遍历该gruop的老鼠,出队相应老鼠
      for(int j=0;j<ng;j++){ 
        //在最后一组老鼠数不足NG起作用，退出循环
        if(  i*ng+j >=temp )  break;  //处理最后一组为不全的退出
        int front=q.front();  //队首老鼠编号
        if(mouse[front].weight > mouse[k].weight) {
          k=front;  //找出质量最大的老鼠
        }
        mouse[front].R=group+1;  //该轮老鼠排名为group+1
        q.pop() ;//出队这只老鼠!!组内遍历每只老鼠最后先出队
      }
      q.push(k);  //胜利的老鼠晋级
    }
    temp=group;  //group只老鼠晋级，因此下轮总老鼠数位group
  }
  mouse[q.front()].R=1;  //当队列只剩下1只老鼠时，令其排名为1
  //输出所有老鼠的信息
  for(int i=0;i<np;i++){ 
    printf("%d",mouse[i].R);
    if(i< np-1)  printf(" ");
  }
  system("pause");
  return 0;
}