PAT甲级 1056 Mice and Rice（25）
文章目录
- 题目
- 题目大意
- 基本思路
- AC代码
- 总结
题目
原题链接
题目大意
给定参赛的老鼠数量为NP，每NG只老鼠分为一组，组中最胖的老鼠获胜，并进入下一轮，所有在本回合中失败的老鼠排名都相同，获胜的老鼠继续每NG只一组，进行比赛，直到决出唯一胜者为止。
输入格式
第一行包含两个整数 NP 和 NG，分别表示老鼠的总数量以及每组老鼠的最大数量。如果分组到最后，剩下不足 NG 只老鼠，则剩下的所有老鼠分为一组。所有 NP 只老鼠的编号为0 ~ NP-1。
第二行包含 NP 个不同的非负整数Wi (i=0,1,…NP-1)，其中 Wi 表示编号为 i 的老鼠的重量。
第三行包含一个0 ~ NP-1的排列，表示老鼠的具体参赛顺序，以样例为例，6号老鼠排在第一个，0号老鼠排在第二个，以此类推。
输出格式
输出一行 NP 个整数，其中第 i 个整数表示编号为 i 的老鼠的最终排名。
数据范围
1 ≤ NP ≤ 1000 ，2 ≤ NG ≤ 1000，0 ≤ Wi ≤ 1000。
基本思路
在进行每轮比赛时，都要先划分小组，在每个小组里选出最重的老鼠进入下一轮比赛，因为每个小组都会筛选出一个最重的老鼠，而其它老鼠的排名就为这轮比赛的组数+1，比如一共有四个老鼠，每组最多三只，则分成两组，每组筛选一个最重的老鼠，就剩下两只老鼠并列第三名(当前组数+1)。还有两只老鼠进入下一轮比赛，因为不足三只，则分成一组，从里面筛选出最重的老鼠成为最终获胜者，则另一只老鼠就为第二名(当前组数+1)。
先定义一个结构体mouse用来存储老鼠的重量和排名，接着定义一个结构体数组m来存储每只老鼠的信息。
struct mouse {
int weight;//重量
int rank;//排名
}m[N];
用一个队列q将每只老鼠的编号按参赛顺序依次入队，使用while循环控制比赛的轮数，当队列只有一只老鼠的编号时，说明已经筛选出最终获胜的老鼠，直接退出循环即可，因此，进入的循环条件为q.size()>1。
在循环里，需要先计算当前的老鼠数量能够分几组，然后再枚举每一组，选出每组中重量最大的老鼠并将其编号记录下来，再将同一组里所有老鼠的排名赋值为当前组数+1，然后将其出队（因为筛选出来的老鼠会进行下一轮比赛，它们的排名会重新变化），再将记录下来的重量最大的老鼠的编号重新进行入队。
注意：
- 因为最后一组的老鼠数量可能不足 NG 只，所以每次筛选出一组中重量最大的老鼠时，要判断当前老鼠的次序是否小于老鼠的总数量，如果大于等于老鼠的总数量则直接退出内层循环。
for (int i = 0; i < group; i++)
{
int t = q.front();
for (int j = 0; j < ng; j++)
{
//判断当前老鼠的次序是否小于老鼠的总数量，如果大于或等于则直接退出循环
if (i * ng + j >= temp)
{
break;
}
int tt = q.front();
if (m[t].weight < m[tt].weight)
{
//更新
t = tt;
}
m[tt].rank = group + 1;
q.pop();
}
q.push(t);
}
- 每轮比赛过后，因为有些老鼠要进入下一轮比赛，所以老鼠的数量都会发生变化，再进行下一轮比赛前（因为要分组），需要将老鼠的总数量更新为当前比赛的组数（因为有几组就会晋升几只老鼠）。
while (q.size() > 1)
{
int group;
if (temp % ng == 0) group = temp / ng;
else group = temp / ng + 1;
for (int i = 0; i < group; i++)
{
int t = q.front();
for (int j = 0; j < ng; j++)
{
//判断当前老鼠的次序是否小于老鼠的总数量，如果大于或等于则直接退出循环
if (i * ng + j >= temp)
{
break;
}
int tt = q.front();
if (m[t].weight < m[tt].weight)
{
//更新
t = tt;
}
m[tt].rank = group + 1;
q.pop();
}
q.push(t);
}
//进入下一轮比赛的老鼠总数量为当前组数
temp = group;
}
AC代码
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1010;
struct mouse {
int weight;//重量
int rank;//排名
}m[N];
int main()
{
int np, ng;
cin >> np >> ng;
int temp = np;
for (int i = 0; i < np; i++)
{
cin >> m[i].weight;
}
queue<int> q;
for (int i = 0; i < np; i++)
{
int x;
cin >> x;
q.push(x);
}
while (q.size() > 1)
{
int group;
if (temp % ng == 0) group = temp / ng;
else group = temp / ng + 1;
for (int i = 0; i < group; i++)
{
int t = q.front();
for (int j = 0; j < ng; j++)
{
//判断当前老鼠的次序是否小于老鼠的总数量，如果大于或等于则直接退出循环
if (i * ng + j >= temp)
{
break;
}
int tt = q.front();
if (m[t].weight < m[tt].weight)
{
//更新
t = tt;
}
m[tt].rank = group + 1;
q.pop();
}
q.push(t);
}
//进入下一轮比赛的老鼠总数量为当前组数
temp = group;
}
//将最终获胜的老鼠的排名记为第一名
m[q.front()].rank = 1;
cout << m[0].rank;
for (int i = 1; i < np; i++)
{
cout << " " << m[i].rank;
}
return 0;
}
在PAT和AcWing平台都通过了
总结
这道题不是难理解，生词也比较少，比较难的是给每只老鼠排名，要结合样例和自己模拟一遍过程得出结论：排名 = 组数 + 1。最后不要忘了更新老鼠的总数量和遍历到当前老鼠的次序不超过总数量即可。