本文主要是介绍PAT甲级真题及训练集(9)--1056. Mice and Rice (25)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1056. Mice and Rice (25)
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 NG 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 NGwinners 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 Wiis 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 3Sample Output:
5 5 5 2 5 5 5 3 1 3 5
提交代码
方案1：（pat测试运行结果正确，但是超时）
/**
作者：一叶扁舟
时间：21:40 2017/6/20
思路：1.首先计算总共要进行PK的总共轮次，9个老鼠要进行3轮次，10-27只老鼠要进行4轮28只老鼠要进行5轮，因此计算公式:m^k >= N; k+1轮，(m为每次m只老鼠进行比拼，N为N只老鼠)2.先将老鼠都都入队列，每次m个老鼠进行比拼，然后在入下一个队列，计算进入下一轮的老鼠个数，然后将上一轮老鼠的名次全部设置为进入下一轮老鼠数量+1，如总共有10老鼠，第一轮结束后，将有4只老鼠进入下一轮，因此将第一轮所有的老鼠的排名变为5（包括将进入下一轮的老鼠），以此类推。直到最后只剩下一只老鼠*/
#include <stdio.h>
#include <string>
#include <stack>
#include <queue>
#include <math.h>
using namespace std;
#define SIZE 10001typedef struct Mouse{int weight;//老鼠的体重int num;//排名
}Mouse;
void updateRank(Mouse *allMouse, int N, Mouse mouse, int rank){for (int i = 0; i < N; i++){if (allMouse[i].weight == mouse.weight){allMouse[i].num = rank;//修改排名}}
}
int main(){int N, M;//总共N只老鼠，每次M只老鼠比拼Mouse mouse[SIZE];queue<Mouse> q;//初始队列queue<Mouse> winQueue;//晋级队列queue<Mouse> markQueue;//对比拼过后的老鼠进行排名int weight;int num;int k = 0;//总共要进行的轮次scanf("%d %d", &N, &M);//计算总共要比拼的次数while (pow(M, k) <= N){k++;}k = k + 1;for (int i = 0; i < N; i++){scanf("%d", &weight);mouse[i].weight = weight;mouse[i].num = 0;//初始化排名}//清空队列while (!q.empty()){q.pop();}//清空晋级队列while (!winQueue.empty()){winQueue.pop();}for (int i = 0; i < N; i++){scanf("%d", &num);//进入操作的队列q.push(mouse[num]);}//核心，真正的开始进行晋级比拼了,总共要进行k轮比赛for (int i = 0; i < k; i++){while (!q.empty()){int j = 0;//取出第一只老鼠Mouse win = q.front();markQueue.push(q.front());q.pop();//每M只老鼠作为一个组for (int j = 0; j < M - 1 && !q.empty(); j++){Mouse next = q.front();markQueue.push(q.front());q.pop();if (next.weight >= win.weight){win.weight = next.weight;win.num = next.num;}}//此时win即为一组中胜出的老鼠，入队winQueue.push(win);}//一轮结束了int rank = winQueue.size();//对当前轮次的进行排名while (!markQueue.empty()){Mouse temp = markQueue.front();markQueue.pop();//修改排名updateRank(mouse, N, temp, rank + 1);}if (rank == 1){//当只有一只老鼠时，就说明比出了第一，所有的比拼结束了Mouse temp = winQueue.front();winQueue.pop();updateRank(mouse, N, temp, rank );break;}else{//将晋级队列中的数据转存到q队列中while (!winQueue.empty()){q.push(winQueue.front());winQueue.pop();}}}//输出结果for (int i = 0; i < N; i++){printf("%d",mouse[i].num);if (i != N - 1){printf(" ");}}system("pause");return 0;
}方案2：（优化的结果，但是pat测试运行结果正确，仍是超时）
/**
作者：一叶扁舟
时间：17:23 2017/6/21
思路：上面的解决方案是正确的，但是在pat测试时，答案正确，超时了。说明时间复杂度比较大，因此在上面的基础上做优化本次优化方案从两个方面考虑：1.不在将每个老鼠数据（老鼠这个对象）放入到队列中，只将第一的编号放入队列中，这样减少了，晋级时修改排名的所浪费的查找时间2.对于排名的计算方式采用了，当前轮次进行分的来计算3.更加1，2优化，再测试时发现仍然超时，因此又进行了第三次优化，将队列转存改为一个队列存储，通过使用一个count来终止一轮的结束，结果还是超时问题，无解了啊，这个我认为是最优解了
*/
#include <stdio.h>
#include <string>
#include <stack>
#include <queue>
#include <math.h>
using namespace std;
#define SIZE 1000001typedef struct Mouse{int weight;//老鼠的体重int num;//排名
}Mouse;
int main(){int N, M;//总共N只老鼠，每次M只老鼠比拼Mouse mouse[SIZE];queue<int> q;//初始队列int group;//每一轮所要分的组int weight;int num;int total;int k = 0;//总共要进行的轮次scanf("%d %d", &N, &M);//计算总共要比拼的次数while (pow(M, k) <= N){k++;}k = k + 1;for (int i = 0; i < N; i++){scanf("%d", &weight);mouse[i].weight = weight;mouse[i].num = 0;//初始化排名}//清空队列while (!q.empty()){q.pop();}for (int i = 0; i < N; i++){scanf("%d", &num);//只将下标编号放入队列中q.push(num);}//核心，真正的开始进行晋级比拼了,总共要进行k轮比赛for (int i = 0; i < k; i++){total = q.size();//本轮循环的总共个数int count = 0;//用来标识本轮已经出队的个数if (q.size() % M == 0){//所有恰好老鼠能够分到一个组中group = q.size() / M ;}else{group = q.size() / M + 1; }while (!q.empty()){int j = 0;//取出第一只老鼠int win = q.front();q.pop();count++;mouse[win].num = group + 1;//当前轮次比赛出队列就可以修改排名了//每M只老鼠作为一个组for (int j = 0; j < M - 1 && count < total; j++){int next = q.front();q.pop();count++;mouse[next].num = group + 1;//当前轮次比赛出队列就可以修改排名了if (mouse[next].weight >= mouse[win].weight){win= next;}}//再入队列队尾q.push(win);if (count == total){break;}}//一轮结束了int rank = q.size();if (rank == 1){//当只有一只老鼠时，就说明比出了第一，所有的比拼结束了int temp = q.front();q.pop();mouse[temp].num = 1;break;}}//输出结果for (int i = 0; i < N; i++){printf("%d", mouse[i].num);if (i != N - 1){printf(" ");}}system("pause");return 0;
}
这篇关于PAT甲级真题及训练集(9)--1056. Mice and Rice (25)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
