PTA甲级 1056 Mice and Rice (25分) 树的遍历

---

title: PTA 1056 Mice and Rice (25分) date: 2020-10-02 15:43:59 tags:

队列queue categories:[刷题,PAT]

---

文章目录

题目原文Input Specification:Output Specification:Sample Input:Sample Output:生词如下: 题目大意:思路如下:算法笔记的代码如下: 强烈推荐,刷PTA的朋友都认识一下柳神–PTA解法大佬

本文由参考于柳神博客写成

柳神的博客,这个可以搜索文章

柳神的个人博客,这个没有广告,但是不能搜索

还有就是非常非常有用的算法笔记

PS 今天也要加油鸭

题目原文

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.

Input Specification:

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.

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

生词如下:

PS:这题我是真的没有看懂,一脸懵逼,就是那种:词我好像都认识,但是连在一起就是不会.

Mice 老鼠

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.

“老鼠和大米”是一个编程竞赛的名称，在这个竞赛中，每个程序员必须编写一段代码来控制给定地图中鼠标的移动。

sake of 为了

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.

意译:

为了简化流程,我们让每个老鼠的重量一开始都是固定好的.老鼠的一开始的顺序也是给定的.你最后要输出程序的结果.

题目大意:

给了你Np只老鼠,还有他们的重量.

然后再给你,他们的初始顺序.

6 0 8 7 10 5 9 1 4 2 3就是代表着 19 25 57 22 10 3 56 18 37 0 46 这个重量顺序

然后要你输出这个顺序下的,老鼠的排名

思路如下:

这个思路是我copy算法笔记的.我自己是想不出来这么好的算法的.

① 开一个结构体mouse用来记录每只老鼠的质量和排名

② 定义一个队列,用来再算法过程中按顺序处理每轮的老鼠

算出下面的几个数据.

每轮比赛把老鼠分成的组数group,设当前轮的参赛老鼠有temp只.如果temp%Ng为0 ,就代表可以整除.group就是temp/Ng 不然的话,group还有加一 .

因为题目讲到了.剩下来的老鼠自己成为一组.

③ 因为每组晋级一只老鼠.所以,每轮晋级的老鼠数量都是group.

没有晋级的老鼠排名都是group+1 —题目讲到了,没有晋级的老鼠排名相同

算法笔记的代码如下:

#include<iostream> #include<queue> #include<vector> using namespace std; struct mouse { int weight; //质量 int R; //排名 }; int main(void) { int Np = 0, Ng = 0, order = 0; cin >> Np >> Ng; vector<mouse> Data(Np); queue<int> p; //创建一个队列 for (int i = 0; i < Np; ++i) scanf("%d", &Data[i].weight); for (int i = 0; i < Np; ++i) { scanf("%d", &order); //题目给出的顺序 p.push(order); //按照顺序,把老鼠们的标号入队 } int temp = Np, group = 0; //temp为当前比赛总老鼠数,group为组数 while (p.size() != 1) { if (temp % Ng == 0) group = temp / Ng; else group = temp / Ng + 1; for (int i = 0; i < group; ++i) { int k = p.front(); //K用来记录每个组里面质量最大的 for (int j = 0; j < Ng; ++j) { //在最后一组老鼠数不足Ng的时起作用.退出循环 if (i * Ng + j >= temp) break; int front = p.front();//队首老鼠编号 if (Data[front].weight > Data[k].weight) k = front; Data[front].R = group + 1; //该轮老鼠排名为group+1 p.pop(); //这只老鼠出队 } p.push(k);//把胜利的老鼠晋级 } temp = group; //group只老鼠晋级.因此下轮总老鼠数为group } Data[p.front()].R = 1; for (int i = 0; i < Np; ++i) { printf("%d", Data[i].R); if (i < Np - 1)printf(" "); } return 0; }

如果这篇文章对你有张帮助的话,可以用你高贵的小手给我点一个免费的赞吗

相信我，你也能变成光.

如果你有任何建议,或者是发现了我的错误,欢迎评论留言指出.