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

注意

  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.rhkb.cn/news/480049.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

[SWPUCTF 2021 新生赛]include

参考博客: 文件包含 [SWPUCTF 2021 新生赛]include-CSDN博客 NSSCTF | [SWPUCTF 2021 新生赛]include-CSDN博客 考点:php伪协议和文件包含 PHP伪协议详解-CSDN博客 php://filter php://filter可以获取指定文件源码。当它与包含函数结合时&#xff0c;php://filter流会被当…

spring boot3.3.5 logback-spring.xml 配置

新建 resources/logback-spring.xml 控制台输出颜色有点花 可以自己更改 <?xml version"1.0" encoding"UTF-8"?> <!--关闭文件扫描 scanfalse --> <configuration debug"false" scan"false"><springProperty …

Unity shaderlab 实现LineSDF

实现效果&#xff1a; 实现代码&#xff1a; Shader "Custom/LineSDF" {Properties{}SubShader{Tags { "RenderType""Opaque" }Pass{CGPROGRAM#pragma vertex vert#pragma fragment frag#include "UnityCG.cginc"struct appdata{floa…

PHP 去掉特殊不可见字符 “\u200e“

描述 最近在排查网站业务时&#xff0c;发现有数据匹配失败的情况 肉眼上完全看不出问题所在 当把字符串 【M24308/23-14F‎】复制出来发现 末尾有个不可见的字符 使用删除键或左右移动时才会发现 最后测试通过 var_dump 打印 发现这个"空字符"占了三个长度 &#xf…

Web会话安全测试

Web会话安全测试 - 知乎 1、会话ID不可预测性 【要求】 会话ID必须采用安全随机算法&#xff08;如SecureRandom&#xff09;生成&#xff0c;并且强度不得低于256位&#xff08;32字符&#xff09;&#xff0c;如采用Tomcat原生JSESSIONID【描述】 密码与证书等认证手段&…

springboot336社区物资交易互助平台pf(论文+源码)_kaic

毕 业 设 计&#xff08;论 文&#xff09; 社区物资交易互助平台设计与实现 摘 要 传统办法管理信息首先需要花费的时间比较多&#xff0c;其次数据出错率比较高&#xff0c;而且对错误的数据进行更改也比较困难&#xff0c;最后&#xff0c;检索数据费事费力。因此&#xff…

富文本编辑器图片上传并回显

1.概述 在代码业务需求中&#xff0c;我们会经常涉及到文件上传的功能&#xff0c;通常来说&#xff0c;我们存储文件是不能直接存储到数 据库中的&#xff0c;而是以文件路径存储到数据库中&#xff1b;但是存储文件的路径到数据库中又会有一定的问题&#xff0c;就是 浏览…

结构体详解+代码展示

系列文章目录 &#x1f388; &#x1f388; 我的CSDN主页:OTWOL的主页&#xff0c;欢迎&#xff01;&#xff01;&#xff01;&#x1f44b;&#x1f3fc;&#x1f44b;&#x1f3fc; &#x1f389;&#x1f389;我的C语言初阶合集&#xff1a;C语言初阶合集&#xff0c;希望能…

学习ASP.NET Core的身份认证(基于Session的身份认证1)

ASP.NET Core使用Session也可以实现身份认证&#xff0c;关于Session的介绍请见参考文献5。基于Session的身份认证大致原理就是用户验证成功后将用户信息保存到Session中&#xff0c;然后在其它控制器中从Session中获取用户信息&#xff0c;用户退出时清空Session数据。百度基于…

题目 3209: 蓝桥杯2024年第十五届省赛真题-好数

一个整数如果按从低位到高位的顺序&#xff0c;奇数位&#xff08;个位、百位、万位 &#xff09;上的数字是奇数&#xff0c;偶数位&#xff08;十位、千位、十万位 &#xff09;上的数字是偶数&#xff0c;我们就称之为“好数”。给定一个正整数 N&#xff0c;请计算从…

人工智能如何改变你的生活?

在我们所处的这个快节奏的世界里&#xff0c;科技融入日常生活已然成为司空见惯的事&#xff0c;并且切实成为了我们生活的一部分。在这场科技变革中&#xff0c;最具变革性的角色之一便是人工智能&#xff08;AI&#xff09;。从我们清晨醒来直至夜晚入睡&#xff0c;人工智能…

MATLAB - ROS2 ros2genmsg 生成自定义消息(msg/srv...)

系列文章目录 前言 语法 ros2genmsg(folderpath)ros2genmsg(folderpath,NameValue) 一、说明 ros2genmsg(folderpath) 通过读取指定文件夹路径下的 ROS 2 自定义信息和服务定义来生成 ROS 2 自定义信息。函数文件夹必须包含一个或多个 ROS 2 软件包。这些软件包包含 .msg 文件…

LeetCode:19.删除链表倒数第N个节点

跟着carl学算法&#xff0c;本系列博客仅做个人记录&#xff0c;建议大家都去看carl本人的博客&#xff0c;写的真的很好的&#xff01; 代码随想录 LeetCode&#xff1a;19.删除链表倒数第N个节点 给你一个链表&#xff0c;删除链表的倒数第 n 个结点&#xff0c;并且返回链表…

探索光耦:光耦安全标准解读——确保设备隔离与安全的重要规范

在现代科技日新月异的今天&#xff0c;光耦&#xff08;光电耦合器&#xff09;作为电子设备中不可或缺的隔离元件&#xff0c;其重要性不言而喻。它不仅在电源调控、工业自动化及医疗设备等关键领域大显身手&#xff0c;更是确保系统电气隔离与运行稳定的守护神。特别是在保障…

ubuntu+ROS推视频流至网络

目录 概述 工具 ros_rtsp 接受流 web_video_server 源码安装 二进制安装 ros接收rtsp视频流 总结 概述 ros_rtsp功能包可以将ros视频流以rtsp形式推送 web_video_server功能包可以将ros视频话题推HTTP流 rocon_rtsp_camera_relay可以接受同一网段下的rtsp视频流输出为…

如何在Python中进行数学建模?

数学建模是数据科学中使用的强大工具&#xff0c;通过数学方程和算法来表示真实世界的系统和现象。Python拥有丰富的库生态系统&#xff0c;为开发和实现数学模型提供了一个很好的平台。本文将指导您完成Python中的数学建模过程&#xff0c;重点关注数据科学中的应用。 数学建…

Hbase2.2.7集群部署

环境说明 准备三台服务器&#xff0c;分别为&#xff1a;bigdata141&#xff08;作为Hbase主节点&#xff09;、bigdata142、bigdata143确保hadoop和zookeeper集群都先启动好我这边的hadoop版本为3.2.0&#xff0c;zookeeper版本为3.5.8 下载安装包 下载链接&#xff1a;In…

【mac】终端左边太长处理,自定义显示名称(terminal路径显示特别长)

1、打开终端 2、步骤 &#xff08;1&#xff09;修改~/.zshrc文件 nano ~/.zshrc&#xff08;2&#xff09;添加或修改PS1&#xff0c;我是自定义了名字为“macminiPro” export PS1"macminiPro$ "&#xff08;3&#xff09;使用 nano: Ctrl o &#xff08;字母…

(长期更新)《零基础入门 ArcGIS(ArcMap) 》实验二----网络分析(超超超详细!!!)

相信实验一大家已经完成了&#xff0c;对Arcgis已进一步熟悉了&#xff0c;现在开启第二个实验 ArcMap实验--网络分析 目录 ArcMap实验--网络分析 1.1 网络分析介绍 1.2 实验内容及目的 1.2.1 实验内容 1.2.2 实验目的 2.2 实验方案 2.3 实验流程 2.3.1 实验准备 2.3.2 空间校正…

云技术-docker

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