1056. Mice and Rice.md

pat 甲级 1056. Mice and Rice

题意概述

给出 Np 只老鼠的质量以及老鼠的初始比较顺序。按初始顺序将老鼠每 Ng 只分成一组，最后不够的 Ng 只单独分成一组。对每组老鼠，质量最大的 1 只晋级，没有晋级的老鼠为同一排名，由于每组晋级一只老鼠，故没有晋级的老鼠的排名为当前组数+1。重复上述步骤直至只剩下一只老鼠，其排名为 1，按编号顺序输出每只老鼠的排名。

输入输出格式

输入第一行包含 2 个正整数：NP 和 NG，分别表示老鼠的总量和一组中的最大老鼠数量。每组最多 NG 只老鼠，所有剩下的老鼠放在最后一组中。第二行包含 NP 个非负整数，表示每个老鼠的重量。第三行给出 NP 个整数，表示初始比较顺序。一行中的所有数字都用空格分隔。

在一行中打印最终排名。第 i 个数字是第 i 个老鼠的排名，所有数字都必须用空格隔开，该行的末尾不能有多余的空格。

数据规模

$$NP,NG<=1000$$

算法设计

可以利用队列进行模拟，每次将所有需比较的老鼠入队。每 NG 只老鼠一组，不够 NG 只的都放到最后一组，选出质量最大的老鼠晋级并重新入队，其余老鼠排名置为组数+1 并不再入队。当队列中只剩下一只老鼠时，该老鼠排名第 1，模拟结束。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg np, ng, ai;
    cin >> np >> ng;
    vector<gg> w(np), ans(np);  //ans记录每只老鼠的排名
    for (gg& i : w) {
        cin >> i;
    }
    queue<gg> q;
    for (gg i = 0; i < np; ++i) {
        cin >> ai;
        q.push(ai);
    }
    while (q.size() > 1) {
        gg group = (q.size() - 1) / ng + 1;  //组数
        gg last = q.size() % ng == 0 ? ng : q.size() % ng;  //最后一组老鼠数量
        for (gg i = 0; i < group; ++i) {
            gg right = (i == group - 1) ? last : ng;  //当前组的老鼠数量
            gg m = q.front();  //记录当前组质量最大的老鼠编号
            for (gg j = 0; j < right; ++j) {
                ans[q.front()] = group + 1;  //默认将当前组的老鼠排名置为组数+1
                if (w[q.front()] > w[m]) {  //记录当前组质量最大的老鼠编号
                    m = q.front();
                }
                q.pop();
            }
            q.push(m);  //当前组质量最大的老鼠晋级，入队
        }
    }
    ans[q.front()] = 1;  //最终剩下的老鼠排名第1
    for (gg i = 0; i < ans.size(); ++i) {
        cout << ans[i] << (i == ans.size() - 1 ? "\n" : " ");
    }
    return 0;
}