PAT甲级1056Mice and Rice
2024-10-21 19:45:18
题目介绍
题目链接
https://pintia.cn/problem-sets/994805342720868352/problems/994805419468242944
题目考点
队列、模拟。重点在模拟,队列只用到了建立、入队、出队、清空(需要自己实现,创建新的队列然后赋值或者
swap
)。题目难度
PAT甲级25分
题目大意
- 给定1个图,每个玩家控制1只老鼠移动,每个老鼠的目标是尽可能多地吃大米变成Fat Mouse。
- \(N_P\)个玩家的顺序是随机的,每\(N_G\)个玩家分成1组进行比赛。每轮的获胜者继续每\(N_G\)个玩家分成一组进行比赛,直到最后1只老鼠。
- 每组中最快的老鼠获胜并进入下一轮,一轮中失败的老鼠的rank(排名)相同。
- 假设每只老鼠的重量是固定的,给出所有大米的重量和玩家初始顺序,请输出每个玩家的rank。
输入
- \(N_P\):玩家的数量,正整数,不超过1000
- \(N_G\):每组中最多有几个玩家(如果剩下的老鼠不够\(N_G\)只,这几只就形成最后一组),正整数,不超过1000
- \(W_i\):\(N_P\)个老鼠的重量,互异的非负数
- \(N_P\)个玩家的顺序,玩家索引为\([0,N_P-1]\)
输出
- 按玩家索引顺序最终所有玩家的rank
题解
解题思路
两个队列:一个保存本轮玩家,一个保存下轮玩家,一直循环到结束(队列里只有1个人)。
关于rank,起初我的想法是通过比赛轮数得到rank,然而发现不行,因为rank要看人数,而不是由在几轮失败决定。
怎么算rank我也想了挺久,后来看了题解才知道:5个人比赛,2个人晋级,那这失败的3个人的rank就是3(即2+1)妙啊。
除了rank,其它部分就比较简单了。
代码
// Problem: PAT Advanced 1056
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/994805419468242944
// Tags:
#include <iostream>
#include <queue>
using namespace std;
int playerNum, playerMaxNumInAGroup; // 玩家数量,1组最多多少玩家
queue<int> nowPlayers, nextPlayers; // 本轮玩家的索引和下轮玩家的索引
int weight[1002]; // 老鼠的重量
int rrank[1002]; // 玩家的排名
int groupNum; // 本轮比赛有多少组
/*一组玩家进行比赛*/
int findFatMouse(){
int maxWeight = weight[nowPlayers.front()], fatMouse = nowPlayers.front();
rrank[nowPlayers.front()] = groupNum + 1;
nowPlayers.pop();
for (int i=1; i < playerMaxNumInAGroup && !nowPlayers.empty(); i++){
if (weight[nowPlayers.front()] > maxWeight){
maxWeight = weight[nowPlayers.front()];
fatMouse = nowPlayers.front();
}
rrank[nowPlayers.front()] = groupNum + 1;
nowPlayers.pop();
}
nextPlayers.push(fatMouse);
}
/*计算本轮比赛有几组*/
int calcGroupNum(){
int nowPlayerNum = nowPlayers.size();
if (nowPlayerNum % playerMaxNumInAGroup == 0)
return nowPlayerNum / playerMaxNumInAGroup;
else
return nowPlayerNum / playerMaxNumInAGroup + 1;
}
int main()
{
// 读取变量
scanf("%d%d", &playerNum, &playerMaxNumInAGroup);
for(int i=0; i < playerNum; i++)
scanf("%d", weight+i);
for(int i=0, player; i < playerNum; i++){
scanf("%d", &player);
nowPlayers.push(player);
}
// 进行比赛
while(nowPlayers.size() > 1){
nextPlayers = queue<int>(); // 清空下一轮比赛的玩家队列
groupNum = calcGroupNum(); // 计算本轮比赛有几组,本轮失败的玩家的rank即为groupNum + 1
for (int i = 0; i < groupNum; i++) // 进行本轮的groupNum组比赛
findFatMouse(); // 一组玩家进行比赛
nowPlayers = nextPlayers; // 进行下一轮比赛,更新玩家队列
}
rrank[nowPlayers.front()] = 1; // 剩下的1个人就是最终的第1名
// 输出排名
printf("%d", rrank[0]);
for (int i = 1; i < playerNum; i++)
printf(" %d", rrank[i]);
return 0;
}
参考链接
Github(github.com):@chouxianyu
Github Pages(github.io):@臭咸鱼
知乎(zhihu.com):@臭咸鱼
博客园(cnblogs.com):@臭咸鱼
B站(bilibili.com):@绝版臭咸鱼
微信公众号:@臭咸鱼的快乐生活
转载请注明出处,欢迎讨论和交流!
最新文章
- git分布式版本控制玩法
- 冰冻三尺非一日之寒--web框架Django
- Ubuntu Server 16.04下ASP.NET Core Web Api + MySql + Dapper在 Jexus、nginx 下的简单测试
- 【转】Web前端浏览器兼容初探
- create和grant配合使用,对Mysql进行创建用户和对用户授权
- 43.Android之ListView中BaseAdapter学习
- iPhone socket 编程之BSD Socket篇
- C++_前置声明
- SQL语言类
- Hello ASP.NET5
- caffe训练超参数
- openstack操作之一 命令行
- 【angularjs】pc端使用angular搭建项目,实现导出excel功能
- 【PyQt5-Qt Designer】窗口操作
- 使用Bootstrap 基于MVC输出移动化table 列表
- 使用Nginx过滤网络爬虫
- 微信小程序绑定数据(微信小程序交流群:604788754)
- JSTORM 问题排查
- 【Shader】这是一篇记录随笔,我要开始学Shader了!
- 最长括号化长度 java
热门文章
- Mybatis Generator 最完整配置详解
- Qt学习笔记-中文乱码-QtWebkit显示网页乱码的问题QFont::setPixelSize: Pixel size <;= 0 (0)
- WebService的简单Demo
- CF Grakn Forces 2020 1408E Avoid Rainbow Cycles(最小生成树)
- eclips如何安装jetty插件
- docker容器中布置静态网站
- Android网络笔记
- 安装Linux Deploy和Termux之后,再安装ftp服务软件都是多余的!
- 切换用户后whoami打印用户的问题
- 【JavaWeb】JavaScript 基础