[PAT A1056]Mice and Rice_综合

[PAT A1056]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 N?P?? programmers. Then every N?G?? programmers 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 N?G?? 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.

输入格式

Each input file contains one test case. For each case, the first line contains 2 positive integers: N?P?? and N?G?? (≤1000), the number of programmers and the maximum number of mice in a group, respectively. If there are less than N?G?? 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 N?P?? distinct non-negative numbers W?i?? (i=0,?,N?P???1) where each W?i?? is the weight of the i-th mouse respectively. The third line gives the initial playing order which is a permutation of 0,?,N?P???1 (assume that the programmers are numbered from 0 to N?P???1). All the numbers in a line are separated by a space.

输出格式

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.

输入样例

11 3

25 18 0 46 37 3 19 22 57 56 10

6 0 8 7 10 5 9 1 4 2 3

输出样例

5 5 5 2 5 5 5 3 1 3 5

解析

这道题目我觉得确实有一定的难度，由于我是第一次做关于队列的题目，所以不知道从何下手，自己第一次写的时候是使用的vector来写的，总分25分只拿了20分，然后自己也是debug了很久，不知道究竟何处错误了。无奈参考晴神代码，最后才自己按照晴神的思路写了一遍。
题目的大致意思就是，首先输入NP和NG，NP表示有多少只老鼠，NG表示每一组老鼠的个数，接下来NP个数是这NP只老鼠的体重，然后第三行是老鼠按照怎样的顺序排列，例如6 0 8……意思就是第一只老鼠是6号，第二只是0号，第三只是8号，依次类推。所以这里绕了个弯，以这题的例子来说，NG=3，说明每三只老鼠进行一次比试，按照比试顺序，并不是0，1，2这三只老鼠比较，而是6 0 8这三只老鼠比较，这个地方没看懂接下来就很难做了。
接下来就是每NG只老鼠进行一次比拼，然后胜利者进入下一轮，相当于一个递归，没进入下一轮的排名一致，例如1，2，3，4，每两两比较，假如第一组1胜了，第二组3胜了，那么2和4排名都是3。1和3需要再次比较才能分出一二名。

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<queue>
using namespace std;
struct mice { //定义老鼠结构体变量，里面包含体重和名次int weight, rank;
};
mice ms[1010];
int main()
{int p, g;              //这里就是NP和NGscanf("%d %d", &p, &g);for (int i = 0; i < p; i++) scanf("%d", &ms[i]);queue<int> q;for (int i = 0; i < p; i++) {int temp;scanf("%d", &temp);q.push(temp);}                      //把老鼠按照序号压入到队列中int num = p, group;while (q.size()!=1)    //如果队列中包含有1个以上的老鼠，则意味着需要再比较一次{group = (num%g == 0) ? num / g : num / g + 1; //如果不能被整除，组数需要再加1for (int i = 0; i < group; i++) {int k = q.front();for (int j = 0; j < g; j++) {if (i*g + j >= num)break; //这里是针对最后一组的情况int front = q.front();if (ms[front].weight > ms[k].weight) k = front;ms[front].rank = group + 1;q.pop();  //每遍历一只老鼠就将其pop出去}q.push(k);//把包含有最大体重的老鼠的序号push到队尾，进行下一次比较}num = group;}ms[q.front()].rank = 1;for (int i = 0; i < p; i++) {printf("%d", ms[i].rank);if (i != p - 1) printf(" ");}return 0;
}