1056. Mice and Rice
Mice and Rice is the name of a programming contest in which each programmer must write a piece of code to control the movements of a mouse in a given map. The goal of each mouse is to eat as much rice as possible in order to become a FatMouse.
First the playing order is randomly decided for NP programmers. Then every NGprogrammers are grouped in a match. The fattest mouse in a group wins and enters the next turn. All the losers in this turn are ranked the same. Every NG winners are then grouped in the next match until a final winner is determined.
For the sake of simplicity, assume that the weight of each mouse is fixed once the programmer submits his/her code. Given the weights of all the mice and the initial playing order, you are supposed to output the ranks for the programmers.
Input Specification:
Each input file contains one test case. For each case, the first line contains 2 positive integers: NP and NG(<= 1000), the number of programmers and the maximum number of mice in a group, respectively. If there are less than NG mice at the end of the player's list, then all the mice left will be put into the last group. The second line contains NP distinct non-negative numbers Wi (i=0,...NP-1) where each Wi is the weight of the i-th mouse respectively. The third line gives the initial playing order which is a permutation of 0,...NP-1 (assume that the programmers are numbered from 0 to NP-1). All the numbers in a line are separated by a space.
Output Specification:
For each test case, print the final ranks in a line. The i-th number is the rank of the i-th programmer, and all the numbers must be separated by a space, with no extra space at the end of the line.
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
题目大意：这是一个比赛中不断分组最终决出胜者的题目。首先给出选手数量np和每组人数ng，然后按序号顺序给出每个选手的分数，接着是以选手序号组成的比赛顺序，按照这个顺序把选手分成不同组，每组有一个优胜者加入下一轮并重复上述分组，而失败者拥有相同的排名并被淘汰。要求输出最终所有选手的排名。
主要思想：思路很简单，利用循环来模拟每轮的比赛，首先需要求出当前轮的组数，然后对于每组成员找出得分最高的选手并将其加入下一轮，将失败者的排名设置为当前组数+1。其中重点是如何更新下一轮的比赛顺序，这里用的是vector容器来储存比赛顺序，将每一组胜者直接覆盖在数组的前端，而下一轮比赛的选手数就是此轮的组数。
#include <iostream>
#include <vector>
using namespace std;
int weight[1000]; //选手得分
int rank_id[1000]; //选手排名
vector<int> order; //比赛顺序
int get_max(int lo, int hi, int p);
int min(int a, int b);
int main(void) {
int np, ng, i;
cin >> np >> ng;
for (i = 0; i < np; i++) {
cin >> weight[i];
}
for (i = 0; i < np; i++) {
int t;
cin >> t;
order.push_back(t);
}
int n = np;
while (true) {
int groups = n / ng; //n是当前轮比赛的人数
int r = n % ng;
if (r > 0) groups++; //求出分组数
int lo = 0, count = 0;
int win_id;
for (i = 0; i < groups; i++) {
int hi = min(lo+ng-1, n-1);
win_id = get_max(lo, hi, groups); //该组的优胜者序号
order[count++] = win_id; //不断更新下一轮的
lo = hi+1;
}
n = groups;
if (n == 1) {
rank_id[win_id] = 1;
break;
}
}
cout << rank_id[0];
for (i = 1; i < np; i++)
cout << " " << rank_id[i];
cout << endl;
return 0;
}
//获得当前组优胜选手的序号，并且把失败者排名设置为group+1
int get_max(int lo, int hi, int p) {
int max_id, i;
int max = 0;
for (i = lo; i <= hi; i++) {
if (max < weight[order[i]]){
max = weight[order[i]];
max_id = order[i];
}
}
for (i = lo; i <= hi; i++) {
if (order[i] != max_id)
rank_id[order[i]] = p + 1;
}
return max_id;
}
int min(int a, int b) {
return a < b ? a : b;
}