1056.md

1056

• 1056 Mice and Rice (25 point(s))

• queue

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;

int P, G;
const int MAX_P = 1e3 + 5;
struct Player {
	int weight;
	int rank;
} ps[MAX_P];

int main() {
	scanf("%d%d", &P, &G);
	for (int p = 0; p < P; p++) {
		scanf("%d", &ps[p].weight);
	}
	queue<int> q;
	for (int p = 0; p < P; p++) {
		int order;
		scanf("%d", &order);
		q.push(order);
	}
	int num = P, group;
	while (q.size() != 1) {
		if (num % G == 0) {
			group = num / G;
		}
		else {
			group = num / G + 1;
		}
		for (int i = 0; i < group; i++) {
			int maxIndex = q.front();
			for (int j = 0; j < G; j++) {
				if (i * G + j >= num) {
					break;
				}
				int front = q.front();
				if (ps[front].weight > ps[maxIndex].weight) {
					maxIndex = front;
				}
				ps[front].rank = group + 1;
				q.pop();
			}
			q.push(maxIndex);
		}
		num = group;
	}
	ps[q.front()].rank = 1;
	for (int i = 0; i < P; i++) {
		printf("%d", ps[i].rank);
		if (i < P - 1) {
			printf(" ");
		}
	}
	printf("\n");
	return 0;
}

/*
Sample Input:
11 3
25 18 0 46 37 3 19 22 57 56 10
6 0 8 7 10 5 9 1 4 2 3
Sample Output:
5 5 5 2 5 5 5 3 1 3 5
*/

References

• 算法笔记