前言

传送门

正文


参考题解

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
/* 题意： np只老鼠，每ng只老鼠为一组(最后不满ng只的老鼠也作为一组)， 每组中重量最重的老鼠可以晋级下一轮比赛，下一轮又按照每ng只老鼠进行分组。 循环往复直到最后只剩一只老鼠。 思路： 1、因为输入给出了初始的order，而下一轮的order又是有本轮的order决定的，因此可以 考虑使用queue（先进先出） 2、每轮比赛可以分多少group，表示晋级下一轮比赛的老鼠个数为group，而本轮被 淘汰的老鼠的名次则为group+1 3、若当前轮比赛的老鼠有cnt只，若cnt%ng==0,则group=cnt/ng；否则说明不能恰好分完， 则group=cnt/ng+1; 4、考虑到输入时需要保存老鼠重量，输出时需要输出每个老鼠的排名，故用结构体进行保存 */
const int N=1e3+10;
struct Mouse{
	int weight,rank; 
}mouse[N];
int main(){
	int np,ng;
	queue<int> q;	
	cin>>np>>ng;
	for(int i=0;i<np;i++){
		scanf("%d",&mouse[i].weight); 
	}
	int order;
	for(int i=0;i<np;i++){
		cin>>order;
		q.push(order);
	}
	int cnt=np,group;//cnt表示本轮老鼠的总数，group表示本轮分几组，同时也是晋级下一轮的老鼠数量
	while(cnt!=1){
		//确定本轮分多少组 
		if(cnt%ng==0)group=cnt/ng;
		else group=cnt/ng+1; 
		//遍历每组，获取晋级下一轮的老鼠编号 
		for(int i=0;i<group;i++){
			int maxW=q.front();//maxW表示本组中重量最重的老鼠编号
			for(int j=0;j<ng;j++){
				//这里需要注意最后一组不足ng只老鼠的情况，就直接退出，否则会出现错误
				//i*ng+j表示下标，故应该是大于等于cnt 
				if(i*ng+j>=cnt)break; 
				int front=q.front();
				if(mouse[front].weight>mouse[maxW].weight){
					maxW=front;
				} 
				mouse[front].rank=group+1;
				q.pop();//该只老鼠出队列 
			}
			q.push(maxW);//将每组获胜的老鼠再次进队列，进入下一轮 
		} 
		cnt=group;//group只老鼠晋级 
	} 
	mouse[q.front()].rank=1;//队列中只剩一只老鼠时，它就是第一名
	printf("%d",mouse[0].rank);
	for(int i=1;i<np;i++){
		printf(" %d",mouse[i].rank);
	} 
	return 0;
}