PAT甲级-1056 Mice and Rice (25分)_综合

点击链接PAT甲级-AC全解汇总

题目：
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

题意：
例子中输入的意思是：
一共有11个数，每3个一组比大小，每组胜出的进入下一轮，不足3人的单独一组
第二行输入是编号0 ~ 10这11个数的值
第三行输入是比较的排序，先6号，再0号。。以此类推
所以：
初始号： 6 0 8 ， 7 10 5 ， 9 1 4 ，2 3
初始数：19 25 57 ， 22 10 3 ，56 18 37 ，0 46
第一轮： 57 ， 22 ，56 ， 46
第二轮： 57 ， 46
第三轮： 57

结果是 57排名1，46排名2，22和56排名并列3，其他都是并列第5
输出0 ~ 10这11个数各自的排名

我的思路：
num[]：存放0 ~ Np 这几个数
rank[]：存放0 ~ Np 这几个数的排名

每一轮过滤掉没有晋级下一轮的，他们的排名都是并列（晋级的人数+1）名
当前一共n人的时候，晋级人数为（ $1+向上取整[n?1Ng]1+向上取整[\frac{n-1}{N_g}]$ ）；
每组晋级的保存到next，一轮结束后把next给now；

注意：每一轮排名都先设置为（ $2+向上取整[n?1Ng]2+向上取整[\frac{n-1}{N_g}]$ ），晋级的人的排名会再各自淘汰的时候更新，最后胜出的最后更新

我的代码：

#include<bits/stdc++.h>
using namespace std;int main()
{
    int Np,Ng;cin>>Np>>Ng;int num[Np]={
    0},rank[Np]={
    0};queue<int>now;for(int i=0;i<Np;i++)cin>>num[i];for(int i=0;i<Np;i++){
    int t;cin>>t;now.push(t);}while(now.size()>1){
    int rank_for_loss=2+ceil((now.size()-1)/Ng);//本轮输者排名int win_id=now.front(),cnt=0;queue<int>next;  //胜者放入next//找出本轮的胜者放到nextwhile(now.size()){
    int id=now.front();now.pop();cnt++;rank[id]=rank_for_loss;//胜者等输了再更新if(num[win_id]<num[id])win_id=id;if(cnt>=Ng||(!now.size())){
    next.push(win_id);if(now.size())win_id=now.front();cnt=0;}}now=next;//更新now}rank[now.front()]=1;//最终的胜者排名为1cout<<rank[0];for(int i=1;i<Np;i++)cout<<" "<<rank[i];return 0;
}