PAT甲级1056Mice and Rice

Posted on | | Visitors:
Words count in article: 938 字 | Reading time ≈ 4 分

[toc]

题目介绍

  • 题目链接

    https://pintia.cn/problem-sets/994805342720868352/problems/994805419468242944

  • 题目考点

    队列、模拟。重点在模拟，队列只用到了建立、入队、出队、清空（需要自己实现，创建新的队列然后赋值或者swap）。

  • 题目难度

    PAT甲级25分

  • 题目大意

    • 给定1个图，每个玩家控制1只老鼠移动，每个老鼠的目标是尽可能多地吃大米变成Fat Mouse。
    • $N_P$个玩家的顺序是随机的，每$N_G$个玩家分成1组进行比赛。每轮的获胜者继续每$N_G$个玩家分成一组进行比赛，直到最后1只老鼠。
    • 每组中最快的老鼠获胜并进入下一轮，一轮中失败的老鼠的rank（排名）相同。
    • 假设每只老鼠的重量是固定的，给出所有大米的重量和玩家初始顺序，请输出每个玩家的rank。

  • 输入

    • $N_P$：玩家的数量，正整数，不超过1000
    • $N_G$：每组中最多有几个玩家（如果剩下的老鼠不够$N_G$只，这几只就形成最后一组），正整数，不超过1000
    • $W_i$：$N_P$个老鼠的重量，互异的非负数
    • $N_P$个玩家的顺序，玩家索引为$[0,N_P-1]$

  • 输出

    • 按玩家索引顺序最终所有玩家的rank

题解

解题思路

  • 两个队列：一个保存本轮玩家，一个保存下轮玩家，一直循环到结束（队列里只有1个人）。

  • 关于rank，起初我的想法是通过比赛轮数得到rank，然而发现不行，因为rank要看人数，而不是由在几轮失败决定。

    怎么算rank我也想了挺久，后来看了题解才知道：5个人比赛，2个人晋级，那这失败的3个人的rank就是3（即2+1）妙啊。

  • 除了rank，其它部分就比较简单了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// Problem: PAT Advanced 1056
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/994805419468242944
// Tags: 

#include <iostream>
#include <queue>
using namespace std;

int playerNum, playerMaxNumInAGroup; // 玩家数量，1组最多多少玩家
queue<int> nowPlayers, nextPlayers;     // 本轮玩家的索引和下轮玩家的索引
int weight[1002]; // 老鼠的重量
int rrank[1002]; // 玩家的排名
int groupNum; // 本轮比赛有多少组


/*一组玩家进行比赛*/
int findFatMouse(){
    int maxWeight = weight[nowPlayers.front()], fatMouse = nowPlayers.front();
    rrank[nowPlayers.front()] = groupNum + 1;
    nowPlayers.pop();

    for (int i=1; i < playerMaxNumInAGroup && !nowPlayers.empty(); i++){
        if (weight[nowPlayers.front()] > maxWeight){
            maxWeight = weight[nowPlayers.front()];
            fatMouse = nowPlayers.front();
        }
        rrank[nowPlayers.front()] = groupNum + 1;
        nowPlayers.pop();
    }
    nextPlayers.push(fatMouse);
}

/*计算本轮比赛有几组*/
int calcGroupNum(){
    int nowPlayerNum = nowPlayers.size();
    if (nowPlayerNum % playerMaxNumInAGroup == 0)
        return nowPlayerNum / playerMaxNumInAGroup;
    else
        return nowPlayerNum / playerMaxNumInAGroup + 1;
}

int main()
{
    // 读取变量
    scanf("%d%d", &playerNum, &playerMaxNumInAGroup);
    for(int i=0; i < playerNum; i++)
        scanf("%d", weight+i);
    for(int i=0, player; i < playerNum; i++){
        scanf("%d", &player);
        nowPlayers.push(player);
    }

    // 进行比赛
    while(nowPlayers.size() > 1){
        nextPlayers = queue<int>(); // 清空下一轮比赛的玩家队列
        groupNum = calcGroupNum();  // 计算本轮比赛有几组，本轮失败的玩家的rank即为groupNum + 1
        for (int i = 0; i < groupNum; i++) // 进行本轮的groupNum组比赛
            findFatMouse(); // 一组玩家进行比赛
        nowPlayers = nextPlayers; // 进行下一轮比赛，更新玩家队列
    }
    rrank[nowPlayers.front()] = 1; // 剩下的1个人就是最终的第1名

    // 输出排名
    printf("%d", rrank[0]);
    for (int i = 1; i < playerNum; i++)
        printf(" %d", rrank[i]);
    return 0;
}

参考链接

Github（github.com）：@chouxianyu

Github Pages（github.io）：@臭咸鱼

知乎（zhihu.com）：@臭咸鱼

博客园（cnblogs.com）：@臭咸鱼

B站（bilibili.com）：@绝版臭咸鱼

微信公众号：@臭咸鱼

转载请注明出处，欢迎讨论和交流!