更多PAT甲级题解--acking-you.github.io

题目

OJ平台

题目翻译

• 这题最大的难点不是别的，就是理解题意！！！

花了很久发现连™给出的示例输出怎么来的都没看懂。

以下均为我得出的关键题意：

1. 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. 最后如果剩下的成员数量不足Ng，则合并为最后一队。
2. 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). 这里说明了第二行输入的是所有老鼠的重量，而且这个重量就是从 i=0...Np-1 的下标顺序代表人员编号，第三行则是当前人员编号的排列，需要以这个为开始！
3. 最重要的一个理解在于对排名的理解--因为题目并未告诉你它的排名规则，我们只能根据实际经验和给出的示例进行猜测！ 排名的方法：举个例子，对于一个已经分成了四个组的情况，最后肯定只会剩下四个人，那么其余所有人的排名就都是第五名，接着继续分组为2组，选出两个人，其余所有人都是2+1 = 3名，继续分组得出一组，选出一个人，则其余所有人都是1+1 = 2名，还剩一个人，故他是冠军，第一名。 总结来说就是和分出多少个组有关！

代码解析

数据展示

int Np, Ng;                             //人数、每组的人数
int *M;                                 //存储原始老鼠编号对应的重量
int *res;                               //存储答案排列
int *P;                                 //存储排列

输入处理

//@输入处理
void Input() {
    ios::sync_with_stdio(false);
    cin >> Np >> Ng;
    M   = new int[Np];
    res = new int[Np];
    P   = new int[Np];
    for (int i = 0; i < Np; i++) {      //输入老鼠重量
        cin >> M[i];
    }
    for (int i = 0; i < Np; i++) {      //输入排列
        cin >> P[i];
    }
}

解决问题核心算法

//@分组核心机制
inline int getGroupSize(int sz) {       //用于计算能形成多少个小组
    return sz / Ng + (sz % Ng == 0 ? 0 : 1);
}
//@答案更新机制
void push_rank(vector<pair<int, int>> &r, int rank) {
    for (int i = 0; i < r.size(); i++) {//用于更新每个成员的排名
        res[r[i].second] = rank;
    }
}


//@解决问题的核心代码
void solve() {                          //利用映射进行模拟
    int Len    = Np;
    int newLen = getGroupSize(Len);
    vector<pair<int, int>> nums(newLen, {-1, -1});
    int rank = newLen + 1;
    fill(res, res + Len, rank);
    int index = 0;                      //更新第第一次nums数组
    for (int i = 0; i < Len; i++) {
        if (i != 0 && i % Ng == 0)
            index++;
        if (M[P[i]] > nums[index].first) {
            nums[index].first  = M[P[i]];
            nums[index].second = P[i];
        }
    }
    vector<pair<int, int>> curNums;     //用nums数组和curNums交替更新，Len记录上一次的数组长度
    while (newLen != 1) {               //若最后只剩下一组，则跳出循环，记得再更新一次答案
        Len    = newLen;
        newLen = getGroupSize(Len);
        rank   = newLen + 1;
        push_rank(nums, rank);
        curNums.resize(newLen);
        int index = 0;
        for (int i = 0; i < Len; i++) {
            if (i != 0 && i % Ng == 0)
                index++;
            if (nums[i].first > curNums[index].first) {
                curNums[index].first  = nums[i].first;
                curNums[index].second = nums[i].second;
            }
        }
        nums = move(curNums);           //转移所有权
    }
    push_rank(nums, 1);                 //最后分成一组后，就跳出了循环，所以最大值并未被更新！
}

输出处理

//@输出处理
void print() {                          //打印操作
    for (int i = 0; i < Np; i++) {
        if (i != Np - 1)
            cout << res[i] << ' ';
        else
            cout << res[i];
    }
}

整合代码提交

#include<bits/stdc++.h>

using namespace std;
int Np, Ng;                             //人数、每组的人数
int *M;                                 //存储原始老鼠编号对应的重量
int *res;                               //存储答案排列
int *P;                                 //存储排列


//@输入处理
void Input() {
    ios::sync_with_stdio(false);
    cin >> Np >> Ng;
    M   = new int[Np];
    res = new int[Np];
    P   = new int[Np];
    for (int i = 0; i < Np; i++) {      //输入老鼠重量
        cin >> M[i];
    }
    for (int i = 0; i < Np; i++) {      //输入排列
        cin >> P[i];
    }
}



//@分组核心机制
inline int getGroupSize(int sz) {       //用于计算能形成多少个小组
    return sz / Ng + (sz % Ng == 0 ? 0 : 1);
}
//@答案更新机制
void push_rank(vector<pair<int, int>> &r, int rank) {
    for (int i = 0; i < r.size(); i++) {//用于更新每个成员的排名
        res[r[i].second] = rank;
    }
}


//@解决问题的核心代码
void solve() {                          //利用映射进行模拟
    int Len    = Np;
    int newLen = getGroupSize(Len);
    vector<pair<int, int>> nums(newLen, {-1, -1});
    int rank = newLen + 1;
    fill(res, res + Len, rank);
    int index = 0;                      //更新第第一次nums数组
    for (int i = 0; i < Len; i++) {
        if (i != 0 && i % Ng == 0)
            index++;
        if (M[P[i]] > nums[index].first) {
            nums[index].first  = M[P[i]];
            nums[index].second = P[i];
        }
    }
    vector<pair<int, int>> curNums;     //用nums数组和curNums交替更新，Len记录上一次的数组长度
    while (newLen != 1) {               //若最后只剩下一组，则跳出循环，记得再更新一次答案
        Len    = newLen;
        newLen = getGroupSize(Len);
        rank   = newLen + 1;
        push_rank(nums, rank);
        curNums.resize(newLen);
        int index = 0;
        for (int i = 0; i < Len; i++) {
            if (i != 0 && i % Ng == 0)
                index++;
            if (nums[i].first > curNums[index].first) {
                curNums[index].first  = nums[i].first;
                curNums[index].second = nums[i].second;
            }
        }
        nums = move(curNums);           //转移所有权
    }
    push_rank(nums, 1);                 //最后分成一组后，就跳出了循环，所以最大值并未被更新！
}




//@输出处理
void print() {                          //打印操作
    for (int i = 0; i < Np; i++) {
        if (i != Np - 1)
            cout << res[i] << ' ';
        else
            cout << res[i];
    }
}

int main() {
    Input();
    solve();
    print();
    return 0;
}