PAT甲级 1056 Mice and Rice(25)

devtools/2024/11/29 18:33:31/

文章目录

  • 题目
  • 题目大意
  • 基本思路
  • 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,然后将其出队因为筛选出来的老鼠会进行下一轮比赛,它们的排名会重新变化),再将记录下来的重量最大的老鼠的编号重新进行入队

注意

  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);
}
  1. 每轮比赛过后,因为有些老鼠要进入下一轮比赛,所以老鼠的数量都会发生变化,再进行下一轮比赛前(因为要分组),需要将老鼠的总数量更新为当前比赛的组数(因为有几组就会晋升几只老鼠)
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最后不要忘了更新老鼠的总数量和遍历到当前老鼠的次序不超过总数量即可


http://www.ppmy.cn/devtools/137987.html

相关文章

学习HTML第三十三天

学习文章目录 一.fieldset 与 legend 的使用&#xff08;了解&#xff09;二.表单总结三.框架标签 一.fieldset 与 legend 的使用&#xff08;了解&#xff09; fieldset 可以为表单控件分组、 legend 标签是分组的标题 二.表单总结 form表单&#xff1a; action 属性&#…

Spring Boot【四】

单例bean中使用多例bean 1.lookup-method方式实现 当serviceB中调用getServiceA的时候&#xff0c;系统自动将这个方法拦截&#xff0c;然后去spring容器中查找对应的serviceA对象然后返回 2.replaced-method&#xff1a;方法替换 我们可以对serviceB这个bean中的getServiceA…

泷羽sec-linux进阶

基础之linux进阶 声明&#xff01; 学习视频来自B站up主 泷羽sec 有兴趣的师傅可以关注一下&#xff0c;如涉及侵权马上删除文章&#xff0c;笔记只是方便各位师傅的学习和探讨&#xff0c;文章所提到的网站以及内容&#xff0c;只做学习交流&#xff0c;其他均与本人以及泷羽…

软件/游戏提示:mfc42u.dll没有被指定在windows上运行如何解决?多种有效解决方法汇总分享

遇到“mfc42u.dll 没有被指定在 Windows 上运行”的错误提示&#xff0c;通常是因为系统缺少必要的运行库文件或文件损坏。以下是多种有效的解决方法&#xff0c;可以帮助你解决这个问题&#xff1a; 原因分析 出现这个错误的原因是Windows无法找到或加载MFC42u.dll文件。这可…

【jvm】什么是动态编译

目录 1. 说明2. 实现方式3. 应用场景 1. 说明 1.在Java中&#xff0c;动态编译指的是在程序运行时动态地编译Java源代码&#xff0c;生成字节码&#xff0c;并加载到JVM&#xff08;Java虚拟机&#xff09;中执行。2.动态编译是在程序运行时&#xff0c;根据需要编译Java源代码…

【Spring源码核心篇-04】spring中refresh刷新机制的流程和实现

Spring源码核心篇整体栏目 内容链接地址【一】Spring的bean的生命周期https://zhenghuisheng.blog.csdn.net/article/details/143441012【二】深入理解spring的依赖注入和属性填充https://zhenghuisheng.blog.csdn.net/article/details/143854482【三】精通spring的aop的底层原…

C#基础题

用C#控制台程序来实现&#xff0c;从键盘输入5个整数&#xff0c;输出其中最大数 输入5个数我们为了方便&#xff0c;可以进行循环&#xff0c;代码如下&#xff1a; int max int.MinValue; for (int i 0; i < 5; i) { Console.WriteLine("请输入第 {0} 个整数:…

不需要双手离开键盘 vscode

目标是“不需要双手离开键盘”&#xff01; ctrl shift O 打开函数导航窗格 ctrl enter 行中换行 alt ↑/↓上下移行 shift alt ↑/↓上下复制 ctrl ←/→ 按代码块移动 ctrl delete / backspace按代码块删除 ctrl l 选择单行 shift delete 删除整行 ctrl C/V 复制/…