PAT甲級1056Mice and Rice
題目介紹
-
題目鏈接
//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: //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）：@絕版臭鹹魚
微信公眾號：@臭鹹魚的快樂生活
轉載請註明出處，歡迎討論和交流!
