1056 Mice and Rice (25 分)

题目

题解

模拟。

看懂题，自己实现就OK了：

代码

#include<bits/stdc++.h>
#define PII pair <int, int>
using namespace std;
const int N = 1e4+10;

int n, gp, o;
int w[N]; // w[i]:编号为i的老鼠的重量 
int level[N]; // 编号为i的老鼠参加的比赛轮数 （轮数越多排名就越靠前） 
int sumlevel[30]; // 参加比赛轮数大于i轮的老鼠的个数，前缀和吧 
vector <PII> thislevel, nextlevel; // 分别保存当前这轮参加比赛的老鼠的信息、获胜的老鼠的信息 

int main()
{
	cin >> n >> gp;
	for (int i = 0;i < n;i ++) cin >> w[i];
	for (int i = 0;i < n;i ++) cin >> o, thislevel.push_back ({w[o], o});	

	int lv = 1;
	while (thislevel.size() != 1) {
		for (int i = 0;i < thislevel.size();i ++) 
			level[thislevel[i].second] = lv; // 先把这轮的老鼠参加的轮数都赋值为lv，最后把获胜的老鼠的level再加一就行了 

		PII tp; // 保存每组最大老鼠的信息 
		for (int i = 0;i < thislevel.size();i ++) {
			if (i % gp == 0) {
				if (i) nextlevel.push_back (tp);
				tp = thislevel[i];
			} else tp = max (tp, thislevel[i]);
		}
		nextlevel.push_back (tp);
		
		for (int i = 0;i < nextlevel.size();i ++)
			level[nextlevel[i].second] = lv + 1; // 获胜的 
		
		sumlevel[lv] = nextlevel.size(); // 参加轮数大于lv的老鼠个数为进入到下一轮的老鼠数量 
		thislevel = nextlevel;
		nextlevel.clear ();
		lv ++;
	}
	
	for (int i = 0, flag = 0;i < n;i ++) {
		if (flag) cout << ' ';
		flag = 1;
		cout << sumlevel[level[i]] + 1;
	}
	
	return 0;
}