PAT 1056 Mice and Rice (25 分)

#include <cstdio> #include <queue> using namespace std; struct mouse { int wei; int r; }mo[1010]; queue<int> qu; int main() { int np,ng,order; scanf("%d%d",&np,&ng); for(int i=0;i<np;i++) scanf("%d",&mo[i].wei); for(int i=0;i<np;i++) { scanf("%d",&order); qu.push(order); } //group为组数 int temp=np,group; while(qu.size()!=1) { //当np能整除ng时 if(temp%ng==0) group=temp/ng; //当np不能整除ng时 else group=temp/ng+1; for(int i=0;i<group;i++) { int k=qu.front(); for(int j=0;j<ng;j++) { //人数超过总人数，跳出 if(i*ng+j>=temp) break; //在一组中选出最重的老鼠，在比较中失败的老鼠名次为组数加1(因为每个组都要选一个优胜者。那么所有失败者名次均为组数加一) int front=qu.front(); if(mo[front].wei>mo[k].wei) k=front; mo[front].r=group+1; //比较完之后，当前组所有老鼠出队 qu.pop(); } //胜利者入队 qu.push(k); } //下一层循环中，老鼠数量等于上一层循环的组数 temp=group; } //最后优胜者名次为1 mo[qu.front()].r=1; for(int i=0;i<np;i++) { printf("%d",mo[i].r); if(i<np-1) printf(" "); } return 0; }