PAT甲级1056 Mice and Rice (25分)|C++实现

一、题目描述

原题链接

Input Specification:

??Output Specification:

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

二、解题思路

运用了队列的题目。进行输入时，我们把输入的比赛顺序存放在一个队列中，需要注意的是，以样例为例，我们前三个输入的6，0，8，意思是6号、0号和8号选手先进行比赛，而不是0号选手是第6个，1号选手是第0个的意思。在队列不为空的情况下，不断进行比赛。首先要分组，我们用tmp表示当前的总人数，group表示分的组数。接着建立一个循环，每$N_G$个程序员就要进行一次比赛，找出最大的，将最大的重新放入队列，其余的排名更新为group+1即可。

三、AC代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn = 1010;
struct Mouse
{
    int weight, R;
}mouse[maxn];
int main()
{
    int Np, Ng, order, tmp;scanf("%d%d", &Np, &Ng);for(int i=0; i<Np; i++)scanf("%d", &mouse[i].weight);queue<int> q;for(int i=0; i<Np; i++){
    scanf("%d", &order);q.push(order);}tmp = Np;int group;while(q.size() != 1){
    if(tmp%Ng == 0) group = tmp / Ng;else    group = tmp/Ng + 1;for(int i=0; i<group; i++){
    int mk = q.front();for(int j=0; j<Ng ; j++){
    if(Ng * i + j + 1 > tmp) break;int front = q.front();if(mouse[front].weight > mouse[mk].weight)  mk = front;mouse[front].R = group + 1;q.pop();}q.push(mk);}tmp = group;}mouse[q.front()].R = 1;for(int i=0; i<Np; i++){
    if(i == 0)  printf("%d", mouse[i].R);else    printf(" %d", mouse[i].R);}return 0;
}