今天无意间看见在必应上搜 1014 题 第二个就是本博客，真的是很开心了。现在 PAT 甲级刷了快 60 题了，复试前刷完 139 题不知道能不能完成。 github 地址：https://github.com/iofu728/PAT-A-by-iofu728 难度：☆☆★ 关键词：模拟，晋级赛

# 题目

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 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. 一开始理解题目出了差错，还是自己英语太差，我以为是总决赛的时候所有名次都会产生。自己脑补分成了小组赛 while 循环和总决赛 sort。导致了三个点错误。
2. 首先给了每个小鼠的体重，初始顺序，我们需要根据初始顺序，把小鼠依次翻到一个容器中（z，z 是我们遍历的顺序数组）。 然后做循环，每NG只老鼠，放到一个 temp 数组中，并进行体重 sort，取出头名，其他名次=（z.size（）平分 ng 的组数+1）。 在这里我用了一个vector的insert来实现取NG个 node 放到 temp 这个过程。 头名放到 x 数组，其余放入 y 数组。 等该轮小组赛结束之后，晋级名单 x 赋给 z。 循环直到晋级“鼠”数小于NG。 然后对总决赛顺序 z 排序，赋名次。
3. 有些博客说这题是queue题，其实我觉得跟queue一点关系都没有，只是每轮小组赛比完之后，会有个晋级名单，把他放在任何一个容器中都行，整个问题 pop 的过程不明显。 我潜意识选用了多个熟悉的vector。关键是分组的实现。

# code

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

struct node {
  int weight, idorigin, rank;
};
bool cmporigin(node a, node b) { return a.idorigin < b.idorigin; }
bool cmpweight(node a, node b) { return a.weight > b.weight; }
int main() {
  int np, ng, id;
  scanf("%d %d", &np, &ng);
  vector<node> v(np), x, y, z; // z遍历列
  for (int i = 0; i < np; ++i) {
    scanf("%d", &v[i].weight);
    v[i].idorigin = i;
  }
  for (int i = 0; i < np; ++i) {
    scanf("%d", &id);
    z.push_back(v[id]);
  }
  //    for(int i=0;i<z.size();++i){
  //        cout<<z[i].idorigin<<' '<<z[i].weight<<endl;
  //    }
  // 分组选优模拟
  while (z.size() > ng) {
    x.clear();
    int postrank = (z.size() - 1) / ng + 2;
    //      cout<<' '<<postrank<<endl;
    // 每组选择
    for (int i = 0; i < z.size(); i = i + ng) {
      vector<node> temp;
      temp.insert(temp.begin(), z.begin() + i,
                  (z.end() >= (z.begin() + i + ng)) ? (z.begin() + i + ng)
                                                    : (z.end()));
      sort(temp.begin(), temp.end(), cmpweight);
      x.push_back(temp[0]);
      //            cout<<"***"<<temp[0].weight<<'
      //'<<temp[0].idorigin<<endl;
      for (int j = 1; j < temp.size(); ++j) {
        temp[j].rank = postrank;
        //              cout<<"###"<<temp[j].weight<<'
        //'<<temp[j].idorigin<<' '<<temp[j].rank<<endl;
        y.push_back(temp[j]);
      }
    }
    z = x;
  }
  sort(z.begin(), z.end(), cmpweight);
  z[0].rank = 1;
  y.push_back(z[0]);
  for (int i = 1; i < z.size(); ++i) {
    z[i].rank = 2;
    //      cout<<"$"<<z[i].weight<<' '<<z[i].idorigin<<'
    //'<<z[i].rank<<endl;
    y.push_back(z[i]);
  }
  sort(y.begin(), y.end(), cmporigin);
  for (int i = 0; i < np - 1; ++i) {
    printf("%d ", y[i].rank);
  }
  printf("%d", y[np - 1].rank);
}