Mice and Rice
is the name of a programming contest in which each programmer must
write a piece of code to control the movements of a mouse in a given
map. The goal of each mouse is to eat as much rice as possible in order
to become a FatMouse.
First the playing order is randomly decided for NP
programmers. Then every NG
programmers are grouped in a match. The fattest mouse in a group wins
and enters the next turn. All the losers in this turn are ranked the
same. Every NG
winners are then grouped in the next match until a final winner is determined.
For the sake of simplicity, assume that the weight of each mouse is
fixed once the programmer submits his/her code. Given the weights of
all the mice and the initial playing order, you are supposed to output
the ranks for the programmers.
[编程题]Mice and Rice (25)
- 热度指数：3625 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
- 算法知识视频讲解
输入描述:
Each input file contains one test case. For each case, the first line contains 2 positive integers: NP and NG (<= 1000), the number of programmers and the maximum number of mice in a group, respectively. If there are less than NG mice at the end of the player's list, then all the mice left will be put into the last group. The second line contains NP distinct non-negative numbers Wi (i=0,...NP-1) where each Wi is the weight of the i-th mouse respectively. The third line gives the initial playing order which is a permutation of 0,...NP-1 (assume that the programmers are numbered from 0 to NP-1). All the numbers in a line are separated by a space.
输出描述:
For each test case, print the final ranks in a line. The i-th number is the rank of the i-th programmer, and all the numbers must be separated by a space, with no extra space at the end of the line.
示例1
输入
11 3 25 18 0 46 37 3 19 22 57 56 10 6 0 8 7 10 5 9 1 4 2 3
输出
5 5 5 2 5 5 5 3 1 3 5
Sample Output:
5 5 5 2 5 5 5 3 1 3 5
一道挺有意思的题目，如果你注意到了第一段里的那个FatMouse就更有意思了，题目的要求是让你模拟一场比赛，n个参赛选手，k人一组，零头不足k也视为一组。然后每轮比赛决出一个冠军，进入下一组，直到最后只剩下一个人。所有在同一轮比赛中输掉的人排名相同，一开始纠结了好久排名应该如何确定，后来想到就是那一轮晋级的人数+1就好了，用pair<int,int>绑定重量与ID，用priority_queue得出胜利者，省下了不少代码。
# include <iostream>
# include <algorithm>
# include <queue>
using namespace std;
const int _size = 1005;
const int debug = 0;
int weight[_size];
int Rank[_size];
typedef pair<int,int> mice;
/*
a struct privided by the head file of algorithm ,
whose member veriables is "first & second",(there refer to "wegiht & id ")
the < operator is defined to attach priority to first
*/
int main()
{
int i,temp;
int n,k,total;
cin >> n >> k;
for (i=0;i<n;i++)
cin >> weight[i];
priority_queue<mice> pri_que;
mice winner[_size];
mice loser[_size];
for (i=0;i<n;i++)
{
cin >> temp;
winner[i] = mice(weight[temp],temp);
}
/**Here is the beginning of the main contest *************************/
total = n; /*We assume every player is the winner of a previous game*/
while (total>1)
{
int e_win = 0;
int e_los = 0;
for (i=0;i<total;i+=k)
{
int begin = i,end = i+k<total?i+k:total;
while (begin<end)
{
pri_que.push(winner[begin]);
begin++;
}
winner[e_win++] = pri_que.top();pri_que.pop();/* by priority_que we can easily find the winner*/
while (!pri_que.empty()) /*After the winner is popped all player left is loser */
{
loser[e_los++] = pri_que.top();
pri_que.pop();
}
}
while (--e_los>=0)
Rank[loser[e_los].second] = e_win + 1;/*All the loser share the same rank which should be bigger than any winner*/
total = e_win;
}
Rank[winner[0].second] = 1;
/**Here is the ending of the main contest *************************/
for (i=0;i<n;i++)
cout << Rank[i] << (i==n-1?'\n':' ');
return 0;
}
编辑于 2015-08-20 00:05:50
回复(3)
更多回答
思路：说实话一开始没有看懂？首先给你一个随机比赛序列（什么你翻译成播放序列，那就很难理解了）。然后每一个NG个数两个比赛 者在一个小组比赛。（小组赛手动滑稽），这个小组最肥的老鼠参加下一场比赛，在这一轮（所有的 小组赛比完）淘汰的赋予排名，胜利的进入下一场比赛。现在你要问，下一场比赛的顺序是什么？ 这里没有讲清楚，还是按照第一次决定的顺序从刚开始诞生，到结束。 题目的意思： 6 0 8 一组 7 10 5 一组 9 1 4 一组 2 3 一组 4组最多诞生4个强人。所以所有淘汰的人排名是 5； 然后 8 7 9 3 作为优胜者参加下一场比赛 8 7 9 一组 3 一组 8 3 一组 8 #include <iostream> #include <vector> #include <deque> #include <fstream> using namespace std; #ifndef Debug ifstream ifile("case.txt"); #define cin ifile #endif struct mice { int weight; int rank; }; /* 11 3 25 18 0 46 37 3 19 22 57 56 10 6 0 8 7 10 5 9 1 4 2 3 */ int main() { int NP, NG; cin >> NP >> NG; vector<struct mice> v(NP); for (int i = 0; i < NP; i++) { cin >> v[i].weight; } deque<int> order(NP); for (int i = 0; i < NP; i++) { cin >> order[i]; } for (; order.size() > 1;) { // 一轮结束 排名删除一些东西 int groupsNumber = order.size() / NG; if (order.size() % NG) { groupsNumber++; } for (int i = 0; i < order.size(); i += NG) { int maxNum = -1; int subScr = -1; for (int j = i; j < i + NG && j < order.size(); j++)// 分组 { if (v[order[j]].weight > maxNum) { if(subScr != -1) { //拉黑 v[order[subScr]].rank = groupsNumber + 1; order[subScr] = -1; } // 赋新值 maxNum = v[order[j]].weight; subScr = j; } else { // 拉黑 v[order[j]].rank = groupsNumber + 1; order[j] = -1; } } } //删除 for (int i = 0; i < order.size(); ) { if (order[i] == -1) { order.erase(order.begin() + i); } else { i++; } } } v[order[0]].rank = 1; for (int i = 0; i < NP; i++) { if (i == 0) cout << v[i].rank; else cout << " " << v[i].rank; } system("pause"); }
发表于 2018-08-27 15:21:53
回复(2)
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = [b[int(i)] for i in input().split()]
d = dict(zip(b,range(a[0])))
e = {i:int((a[0] - 1) // a[1] + 2) for i in range(a[0])}
while len(c) - 1:
c = [max(c[i:i + a[1]]) for i in range(0,len(c),a[1])]
e.update({d[i]:(len(c) - 1) // a[1] + 2 for i in c})
e[d[c[0]]] = 1
print(' '.join(map(str,list(e.values()))))
题目本身不难，一步到位
第一排的两个数a，b分别表示总人数和每组的最大人数（非最大人数只可能出现在末组），那么经过第一次比赛，(a - 1) // b + 2可以直接得到没有晋级的排名
然后更新a的值为晋级成功的总人数，那么现在(a - 1) // b + 2依然是没有晋级的排名，以此类推，可以获得除了第1名之外的所有正确排名，然后手动给最后晋级的成员赋值排名1
这样的话可以节省不少代码
编辑于 2020-03-05 21:40:28
回复(0)
java清晰解答，分享给大家，有问题咨询shr834162
import java.util.*;
/**
* Copyright (C), 2019-2020, CPS Lab
*
* @ProjectName: PATProjects
* @Package: PACKAGE_NAME
* @ClassName: PAT1016
* @Author: Tristan Shu
* @CreateDate: 2020/10/16 11:13 上午
* @Version: 1.0
*/
public class PAT1016 {
private static int Np;
private static int Ng;
private static int[] rank;
private static List<Mice> loseList;
private static List<Mice> winList;
private static List<Mice> contestList;
private static List<Mice> infoList;
private static class Mice{
private int master;
private int weight;
private Mice(int master,int weight){
this.master = master;
this.weight = weight;
}
}
private static class MiceCompare implements Comparator<Mice>{
@Override
public int compare(Mice o1, Mice o2) {
return Integer.compare(o1.weight, o2.weight);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Np = sc.nextInt();
Ng = sc.nextInt();
loseList = new LinkedList<>();
winList = new LinkedList<>();
contestList = new LinkedList<>();
infoList = new LinkedList<>();
rank = new int[Np];
for(int i = 0; i < Np; i++){
infoList.add(new Mice(i,sc.nextInt()));
}
for (int i = 0; i < infoList.size(); i++) {
winList.add(i,infoList.get(sc.nextInt()));
}
//contest begins
int total = Np;
while (total > 1){
int winNum = 0;
//the first round
for (int i = 0; i < total; i+=Ng) {
int start = i;
int end = Math.min(i + Ng, total);
while(start < end){
contestList.add(winList.get(start));
start++;
}
Collections.sort(contestList,new MiceCompare());
winList.set(winNum++, contestList.remove(contestList.size() - 1));
while (contestList.size() > 0){
loseList.add(contestList.remove(0));
}
}
//Set the rank of losers of this round
while (loseList.size() > 0){
rank[loseList.remove(0).master] = winNum + 1;
}
total = winNum;
}
rank[winList.get(0).master] = 1;
for (int i = 0; i < rank.length; i++) {
System.out.print(rank[i]);
if(i != rank.length - 1){
System.out.print(" ");
}
}
}
}
发表于 2020-10-18 15:09:29
回复(0)
这考试的题难度全在理解题意上：
1.Programmer和Mice混在一起，背景故事也是用来误导的。
2.initial playing order指的是什么？6 0 8我可不可以理解为0号猫丝第6个上，1号猫丝第0个上，2号猫丝第8个上？
3.rank怎么算也不讲清楚？四轮分出胜负，我想了半天才搞明白样例是怎么出现5的。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Mice {
int order;
int w;
int id;
Mice(int order, int w, int id): order(order), w(w), id(id){}
};
bool operator <(const Mice& lhs, const Mice& rhs){
return lhs.order < rhs.order;
}
int main(){
int Np, Ng;
cin >> Np >> Ng;
vector<int> ws(Np);
for(int i = 0; i < Np; i++){
cin >> ws[i];
}
vector<Mice> ms;
// vector<int> orders(Np);
for(int i = 0; i < Np; i++){
int order;
cin >> order;
ms.emplace_back(0, ws[order], order);
}
// sort(begin(ms), end(ms));
vector<Mice> next_round;
int level = 0;
vector<int> levels(Np), level_cnt(Np);
while((int)ms.size() > 1){
// cout << "ms:" << endl;
// for(auto& m : ms){
// cout << m.w << " ";
// }
// cout << endl;
int n = ms.size();
int k = 0;
while(k < n){
int max_w = -1, max_idx = 0;
for(int i = k; i < k + Ng && i < n; i++){
if(ms[i].w > max_w){
max_w = ms[i].w;
max_idx = i;
}
}
for(int i = k; i < k + Ng && i < n; i++){
if(i != max_idx){
levels[ms[i].id] = level;
}
else{
levels[ms[i].id] = level + 1;
}
}
next_round.push_back(ms[max_idx]);
k += Ng;
}
level++;
swap(ms, next_round);
next_round.clear();
// sort(begin(ms), end(ms));
}
for(int i = 0; i < Np; i++){
level_cnt[levels[i]]++;
}
vector<int> ranks(Np);
int rank = 1;
for(int i = level; i >= 0; i--){
ranks[i] = rank;
rank += level_cnt[i];
}
for(int i = 0; i < Np; i++){
if(i) cout << " ";
cout << ranks[levels[i]];
}
cout << endl;
}
发表于 2019-08-27 01:50:06
回复(0)
//题目的坑爹之处在于，没讲清楚第三行order的含义。
//搞了半天
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>#include <algorithm>
#include <vector>
#include <map>
using namespace std;
//1056 Mice and Rice
//结点编号0~np-1
vector<int> w;
int score[1005] = {};
map<int, int> order2id;
int get_winner(const int &start, const int &end) {
int maxx = -1, maxxid = 0;
for (int i = start; i < end; ++i) {
if (w[order2id[i]] > maxx) {
maxx = w[order2id[i]];
maxxid = order2id[i];
}
}
return maxxid;
}
int main() {
int np, ng, val;
cin >> np >> ng;
for (int i = 0; i < np; ++i) {
cin >> val;
w.push_back(val);
}
for (int i = 0; i < np; ++i) {
//sb题目
//6 0 8 7 10 5 9 1 4 2 3
//我一开始以为，第0个6表示第6个出场的是0号元素，第1个0表示第0个出场的是1号元素。
//后来发现，第0个6表示，第0个出场的是6号元素，第1个0表示第1个出场的是0号元素。
cin >> val;
//order2id[val] = i;
order2id[i] = val;
}
int round = 0;
int remain = np;
while (remain > 1) {
//第round轮
int winner, cnt = 0;
map<int, int> tmp;
//遍历group，求胜者
for (int i = 0; i < remain; i += ng) {
if (i + ng < remain) { winner = get_winner(i, i + ng); }
else { winner = get_winner(i, remain); }
score[winner] += 1; //胜者加分，败者食尘。
tmp[cnt++] = winner; //下一轮的次序
}
//本轮结束
order2id = tmp;
remain = tmp.size();
}
//最后一人，分数再加一分。
score[order2id[0]] += 1;
//分数降序
vector<int> score_v(score, score + np);
sort(score_v.begin(), score_v.end(), greater<int>());
//制造排名
map<int, int> ranking;
int rk = 1, pre_score = 0;
for (int i = 0; i < np; ++i) {
if (score_v[i] != pre_score) {
rk = i + 1;
pre_score = score_v[i];
ranking[score_v[i]] = rk;
}
//如果和上一个同分，则rk不变，并列排名
}
//输出排名
cout << ranking[score[0]];
for (int i = 1; i < np; ++i) {
cout << " " << ranking[score[i]];
}
return 0;
}
发表于 2019-08-17 16:05:29
回复(0)
使用 queue 来演算每一回合的情况，每回合会有group个 winner，那么 loser 的排名就是group + 1。然后我用指针优化了一下。。。
参考：https://www.liuchuo.net/archives/2936
/**
* Mice and Rice(25)
*
* Queue
*/
#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
struct Player {
int weight, rank;
};
int main() {
int np, ng;
scanf("%d%d", &np, &ng);
int order[np];
Player players[np];
for (int i = 0; i < np; i++) {
scanf("%d", &players[i].weight);
}
for (int i = 0; i < np; i++) {
scanf("%d", &order[i]);
}
queue<Player *> q;
for (int i = 0; i < np; i++) {
q.push(&players[order[i]]);
}
while (!q.empty()) {
int size = q.size();
if (size == 1) {
Player *tmp = q.front();
tmp->rank = 1;
break;
}
int group = size / ng + (size % ng == 0 ? 0 : 1);
Player *max;
int maxn = -1, cnt = 0;
for (int i = 0; i < size; i++) {
Player *tmp = q.front();
// <group> players will win, so losers' rank is <group + 1>
tmp->rank = group + 1;
q.pop();
cnt++;
if (tmp->weight > maxn) {
maxn = tmp->weight;
max = tmp;
}
// next group
if (cnt == ng || i == size - 1) {
cnt = 0;
maxn = -1;
q.push(max);
}
}
}
for (int i = 0; i < np; i++) {
if (i != 0) printf(" ");
printf("%d", players[i].rank);
}
return 0;
}
编辑于 2019-04-15 17:14:38
回复(0)
/*
https://www.nowcoder.com/questionTerminal/667e3c519c30492fbb007fbb42f44bff
Mice and Rice (25) 2018-12-21
General Mean: Tell you the weight and order of some mice join in the game, require the rank of those mice in the result of game.
Result: Cost me more than tow hours, after understanding the question, I use a poriority_queue and a que to simulate the process
of this game, but when i use pop() of poriority_queue, something happen and it report an error So i got to use other method. My
idea is right but when it come to coding, a lot of mistake have benn made in many of the details, tired to debug and time have
gone. Anyway, it is an simple and funny problem, I want to solve it by tree last time!
*/
https://www.nowcoder.com/questionTerminal/667e3c519c30492fbb007fbb42f44bff
Mice and Rice (25) 2018-12-21
General Mean: Tell you the weight and order of some mice join in the game, require the rank of those mice in the result of game.
Result: Cost me more than tow hours, after understanding the question, I use a poriority_queue and a que to simulate the process
of this game, but when i use pop() of poriority_queue, something happen and it report an error So i got to use other method. My
idea is right but when it come to coding, a lot of mistake have benn made in many of the details, tired to debug and time have
gone. Anyway, it is an simple and funny problem, I want to solve it by tree last time!
*/
#include"stdafx.h"
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<stack>
using namespace std;
const int maxn = 1009;
struct mice{
int rank = 0; //it is not the rank in result but how the times join in the game
int weight;
}player[maxn];
queue<int>order;
int sum, per;
int tongji[maxn]; //statistics of total munber of mice in different rank.
int ans[maxn]; //
int main(){
cin >> sum >> per;
for (int i = 0; i < sum; i++) cin >> player[i].weight;
for (int t, i = 0; i < sum; i++){
cin >> t;
order.push(t);
}
while (order.size() > 1){ //my mistake mainly made in it circulation
int need = per;
int winer_index=0, winer_weight=-10000;
int aRank = player[order.front()].rank;
int bRank = player[order.front()].rank;
while (need>0 && aRank == bRank){ // I code aRamk==aRank by mistake and debuge for 30 minues. stupid...
int i = order.front();
if (winer_weight < player[i].weight){
winer_weight = player[i].weight;
winer_index = i;
}
order.pop();
need--;
if (order.empty()) break; //forgot to check is one of those mistake.
bRank = player[order.front()].rank;
}
player[winer_index].rank++;
order.push(winer_index);
}
for (int i = 0; i < sum; i++) tongji[player[i].rank]++; //translate join-times to rank
for (int s=0, rank = sum-1; rank >=0; rank--){
ans[rank] = s+1;
s += tongji[rank];
}
for (int i = 0; i < sum-1; i++) cout << ans[player[i].rank] << " ";
cout << ans[player[sum-1].rank] << endl;
return 0;
}
发表于 2018-12-21 11:20:07
回复(0)
#include <iostream>
#include <queue>
using namespace std;
queue<int> q;
//seq按顺序存放每个mice的重量,wins存放不同重量所获胜的次数
int seq[1000000], wins[1000000];
int main() {
int n, m, temp;
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++) {
scanf("%d", &seq[i]);
}
for (int i = 0; i < n; i++) {
scanf("%d", &temp);
q.push(seq[temp]);
}
int max_mice = 0, count = 0, len = n, j = 0, round = 0, rank[1000];
while (j < len) {
temp = q.front();
q.pop();
max_mice = max(max_mice, temp);
count++; // 记录一组中遍历的个数
// 一轮结束
if (j == len - 1) {
q.push(max_mice);
wins[max_mice] += 1;
max_mice = 0;
count = 0;
j = 0;
rank[round] = q.size() + 1; // 记录每轮中淘汰的老鼠的排名(第一名需特判)
round++; // 记录轮次
len = q.size();
if (len == 1) break; // 这里如果len等于1后会死循环,需特判退出
continue;
}
// 一组结束
if (count == m) {
q.push(max_mice);
wins[max_mice] += 1;
max_mice = 0;
count = 0;
}
j++;
}
// 输出
for (int i = 0; i < n; i++) {
temp = wins[seq[i]];
if (rank[temp] == 0) {
printf("1"); // 对第一名特判
} else {
printf("%d", rank[temp]);
}
if (i != n - 1) printf(" ");
}
return 0;
}
发表于 2023-04-09 10:35:41
回复(0)
#include<bits/stdc++.h>
using namespace std;
const int Max=1010;
struct mouse {
int w;
int r;
} a[Max];
int main() {
int n,m,x;
cin>>n>>m;
for(int i=0; i<n; i++) {
cin>>a[i].w;
}
queue<int> q;
for(int i=0; i<n; i++) {
cin>>x;
q.push(x);
}
int total=n,graph;
while(q.size()!=1) {
if(total%m==0) graph=total/m;
else graph=total/m+1;
for(int i=0; i<graph; i++) {
int Maxi=q.front();
for(int j=0; j<m; j++) {
if(i*m+j>=total) break;
int s=q.front();
if(a[s].w>a[Maxi].w) {
Maxi=s;
}
a[s].r=graph+1;
q.pop();
}
q.push(Maxi);
}
total=graph;
}
a[q.front()].r=1;
for(int i=0; i<n; i++) {
cout<<a[i].r;
if(i<n-1) cout<<" ";
}
return 0;
}
发表于 2022-11-21 14:10:25
回复(0)
更多PAT甲级题解--acking-you.github.io
题目
题目翻译
- 这题最大的难点不是别的，就是理解题意！！！
花了很久发现连™给出的示例输出怎么来的都没看懂。
以下均为我得出的关键题意：
- If there are less than Ng mice at the end of the player's list, then all the mice left will be put into the last group.
最后如果剩下的成员数量不足Ng，则合并为最后一队。- The second line contains NP distinct non-negative numbers Wi (i=0,...NP-1) where each Wi is the weight of the i-th mouse respectively. The third line gives the initial playing order which is a permutation of 0,...NP-1 (assume that the programmers are numbered from 0 to NP-1).
这里说明了第二行输入的是所有老鼠的重量，而且这个重量就是从 i=0...Np-1 的下标顺序代表人员编号，第三行则是当前人员编号的排列，需要以这个为开始！- 最重要的一个理解在于对排名的理解--因为题目并未告诉你它的排名规则，我们只能根据实际经验和给出的示例进行猜测！
排名的方法：举个例子，对于一个已经分成了四个组的情况，最后肯定只会剩下四个人，那么其余所有人的排名就都是第五名，接着继续分组为2组，选出两个人，其余所有人都是2+1 = 3名，继续分组得出一组，选出一个人，则其余所有人都是1+1 = 2名，还剩一个人，故他是冠军，第一名。
总结来说就是和分出多少个组有关！
代码解析
数据展示
int Np, Ng; //人数、每组的人数 int *M; //存储原始老鼠编号对应的重量 int *res; //存储答案排列 int *P; //存储排列
输入处理
//@输入处理
void Input() {
ios::sync_with_stdio(false);
cin >> Np >> Ng;
M = new int[Np];
res = new int[Np];
P = new int[Np];
for (int i = 0; i < Np; i++) { //输入老鼠重量
cin >> M[i];
}
for (int i = 0; i < Np; i++) { //输入排列
cin >> P[i];
}
} 解决问题核心算法
//@分组核心机制
inline int getGroupSize(int sz) { //用于计算能形成多少个小组
return sz / Ng + (sz % Ng == 0 ? 0 : 1);
}
//@答案更新机制
void push_rank(vector<pair<int, int>> &r, int rank) {
for (int i = 0; i < r.size(); i++) {//用于更新每个成员的排名
res[r[i].second] = rank;
}
}
//@解决问题的核心代码
void solve() { //利用映射进行模拟
int Len = Np;
int newLen = getGroupSize(Len);
vector<pair<int, int>> nums(newLen, {-1, -1});
int rank = newLen + 1;
fill(res, res + Len, rank);
int index = 0; //更新第第一次nums数组
for (int i = 0; i < Len; i++) {
if (i != 0 && i % Ng == 0)
index++;
if (M[P[i]] > nums[index].first) {
nums[index].first = M[P[i]];
nums[index].second = P[i];
}
}
vector<pair<int, int>> curNums; //用nums数组和curNums交替更新，Len记录上一次的数组长度
while (newLen != 1) { //若最后只剩下一组，则跳出循环，记得再更新一次答案
Len = newLen;
newLen = getGroupSize(Len);
rank = newLen + 1;
push_rank(nums, rank);
curNums.resize(newLen);
int index = 0;
for (int i = 0; i < Len; i++) {
if (i != 0 && i % Ng == 0)
index++;
if (nums[i].first > curNums[index].first) {
curNums[index].first = nums[i].first;
curNums[index].second = nums[i].second;
}
}
nums = move(curNums); //转移所有权
}
push_rank(nums, 1); //最后分成一组后，就跳出了循环，所以最大值并未被更新！
} 输出处理
//@输出处理
void print() { //打印操作
for (int i = 0; i < Np; i++) {
if (i != Np - 1)
cout << res[i] << ' ';
else
cout << res[i];
}
} 整合代码提交
#include<bits/stdc++.h>
using namespace std;
int Np, Ng; //人数、每组的人数
int *M; //存储原始老鼠编号对应的重量
int *res; //存储答案排列
int *P; //存储排列
//@输入处理
void Input() {
ios::sync_with_stdio(false);
cin >> Np >> Ng;
M = new int[Np];
res = new int[Np];
P = new int[Np];
for (int i = 0; i < Np; i++) { //输入老鼠重量
cin >> M[i];
}
for (int i = 0; i < Np; i++) { //输入排列
cin >> P[i];
}
}
//@分组核心机制
inline int getGroupSize(int sz) { //用于计算能形成多少个小组
return sz / Ng + (sz % Ng == 0 ? 0 : 1);
}
//@答案更新机制
void push_rank(vector<pair<int, int>> &r, int rank) {
for (int i = 0; i < r.size(); i++) {//用于更新每个成员的排名
res[r[i].second] = rank;
}
}
//@解决问题的核心代码
void solve() { //利用映射进行模拟
int Len = Np;
int newLen = getGroupSize(Len);
vector<pair<int, int>> nums(newLen, {-1, -1});
int rank = newLen + 1;
fill(res, res + Len, rank);
int index = 0; //更新第第一次nums数组
for (int i = 0; i < Len; i++) {
if (i != 0 && i % Ng == 0)
index++;
if (M[P[i]] > nums[index].first) {
nums[index].first = M[P[i]];
nums[index].second = P[i];
}
}
vector<pair<int, int>> curNums; //用nums数组和curNums交替更新，Len记录上一次的数组长度
while (newLen != 1) { //若最后只剩下一组，则跳出循环，记得再更新一次答案
Len = newLen;
newLen = getGroupSize(Len);
rank = newLen + 1;
push_rank(nums, rank);
curNums.resize(newLen);
int index = 0;
for (int i = 0; i < Len; i++) {
if (i != 0 && i % Ng == 0)
index++;
if (nums[i].first > curNums[index].first) {
curNums[index].first = nums[i].first;
curNums[index].second = nums[i].second;
}
}
nums = move(curNums); //转移所有权
}
push_rank(nums, 1); //最后分成一组后，就跳出了循环，所以最大值并未被更新！
}
//@输出处理
void print() { //打印操作
for (int i = 0; i < Np; i++) {
if (i != Np - 1)
cout << res[i] << ' ';
else
cout << res[i];
}
}
int main() {
Input();
solve();
print();
return 0;
}
发表于 2021-09-30 20:38:36
回复(0)
题目就难在理解题意。写起来很简单，rank的值得想一会儿怎么来的，题目也没写明白。
#include <iostream>
#include <vector>
using namespace std;
int total_num,grop_num;
vector<int> mice_w;
vector<int> list1;
vector<int> list2;
vector<int> rank_list;
void mice_rank(int rank){
while (list1.size()) {
int t_w=0,t_n=0,g_n=0;
g_n=(list1.size()>=grop_num?grop_num:int(list1.size()));
for (int i=0; i<g_n; i++) {
if (mice_w[list1[i]]>t_w) {
t_w=mice_w[list1[i]];
t_n=list1[i];
}
}
list2.push_back(t_n);
for (int i=0; i<g_n; i++) {
if (list1[i]!=t_n) {
rank_list[list1[i]]=rank;
}
}
list1.erase(list1.begin(),list1.begin()+g_n);
}
for (int i=0; i<list2.size(); i++) {
list1.push_back(list2[i]);
}
list2.clear();
}
int main(int argc, const char * argv[]) {
int temp1,temp2,rank;
cin>>total_num>>grop_num;
for (int i=0; i<total_num; i++) {
cin>>temp1;
mice_w.push_back(temp1);
}
for (int i=0; i<total_num; i++) {
cin>>temp2;
list1.push_back(temp2);
rank_list.push_back(0);
}
while (list1.size()>1) {
if (list1.size()%grop_num==0)
rank=int(list1.size()/grop_num+1);
else
rank=int(list1.size()/grop_num+2);
mice_rank(rank);
}
rank_list[list1[0]]=1;
for (int i=0; i<rank_list.size(); i++) {
cout<<rank_list[i];
if (i!=rank_list.size()-1) {
cout<<" ";
}
}
return 0;
}
发表于 2021-02-21 16:38:03
回复(0)
//Mice and Rice (25分)
#include <iostream>
(720)#include <vector>
#include <algorithm>
using namespace std;
int n, m, weight[1002], ranks[1002], flag = 0;
vector<int> arrays, temporary;
bool comp(int &a, int &b) {
return weight[a] > weight[b];
}
void getRanks() {
if (arrays.size() <= m) {
sort(arrays.begin(), arrays.end(), comp);
ranks[arrays[0]]=1;
for (int i = 1; i < arrays.size(); i++) {
ranks[arrays[i]] = 2;
}
flag = 1;
} else {
int x = ((arrays.size() % m) == 0) ? arrays.size() / m : (arrays.size() / m) + 1;
int index = 0;
for (int i = 0; i < x; i++) {
int number = ((arrays.size() - index)) < m ? (arrays.size() - index) : m;
sort(arrays.begin() + index, arrays.begin() + index + number, comp);
for (int j = index + 1; j < index + number; j++)
ranks[arrays[j]] = x + 1;
temporary.push_back(arrays[index]);
index += number;
}
arrays.clear();
arrays = temporary;
temporary.clear();
}
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++)
scanf("%d", &weight[i]);
for (int i = 0; i < n; i++) {
int q;
scanf("%d", &q);
arrays.push_back(q);
}
while (true) {
if (flag == 1) break;
getRanks();
}
for (int i = 0; i < n; i++) {
if (i != 0) printf(" %d", ranks[i]);
else printf("%d", ranks[i]);
}
}
发表于 2020-03-31 10:28:02
回复(0)
不难，但是题目意思有点绕而且麻烦。用优先队列
#include<iostream>// 0,10,9,3
(1082)#include<vector>
using namespace std;
#include<queue>
vector<int>grades;
vector<int>priority;
vector<int>current;
int main() {
//freopen("C:\\Users\\47\\Desktop\\1.txt", "r", stdin);
int n, m, index;
priority_queue<int>myQueue;
cin >> n >> m;
vector<int>rank(n);
for (int i = 0; i < n; i++) {
int x;
cin >> x;
grades.push_back(x);
}
for (int i = 0; i < n; i++) {
int x;
cin >> x;
priority.push_back(x);
}
for (int i = 0; i < n; i++) {//总共比较多少轮
vector<int>next;//保存下一轮的priority
int rankNumber = priority.size() / m +1;//每一轮的失败人数的排名应该是晋级下一轮的人数再加一
if (priority.size() % m != 0) { rankNumber++; }
int num = 0;
for (int j = 0; j < priority.size(); j++) {//每一轮遍历priority数组
myQueue.push(grades[priority[j]]);
num++;
if (num == m || j == priority.size() - 1) {
num = 0;
int k = 0;
int maxNumber = myQueue.top();
if (myQueue.size() != m) {
k = j - myQueue.size() + 1;
}
else {
k = j - m + 1;
}
while (!myQueue.empty()) {
myQueue.pop();
}
for (; k <= j; k++) {
if (grades[priority[k]] != maxNumber) {
rank[priority[k]] = rankNumber;
}
else {
next.push_back(priority[k]);
}
}
}
}
if (next.size() == 1) {
rank[next[0]] = 1;
break;
}
else {
priority = next;
}
}
for (int i = 0; i < n; i++) {
if (i) printf(" ");
printf("%d", rank[i]);
}
}
发表于 2020-02-28 14:21:09
回复(0)
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdio>
using namespace std;
int p,g;
const int maxn = 1007;
typedef struct mouse {
int num,weight,sequence,rank;
bool operator < (const mouse& m) const {
return weight < m.weight;
}
} mouse;
mouse mice[maxn];
bool cmp(const mouse &a, const mouse &b) { // 按参加顺序排序，为进队列做准备
return a.sequence < b.sequence;
}
bool icmp(const mouse &a, const mouse &b) { // 排回来，为输出做准备
return a.num < b.num;
}
priority_queue<mouse> Q; // 每次丢进去g只老鼠得到其中最大的
queue<mouse> QQ; // 存放尚未编号的老鼠
int e;
int main() {
cin >> p >> g;
for(int i = 0; i < p; ++i) {
cin >> mice[i].weight;
mice[i].num = i;
}
int seq;
for(int i = 0; i < p; ++i) {
cin >> seq;
mice[seq].sequence = i;
}
sort(mice,mice+p,cmp);
for(int i = 0; i < p; ++i)
QQ.push(mice[i]);
int cur = p; // cur表示每一轮需要处理的老鼠数量
while(cur > 1) { // 要处理的耗子大于一只
int circles = cur/g + ((cur%g>0)?1:0); // 这一轮要处理几批老鼠
int rank = circles+1;
for(int i = 0; i < circles; ++i) {
for(int j = 0; j < g && i*g+j < cur; ++j) { // 选取g只或剩余不足g只耗子丢进优先队列
temp = QQ.front();
QQ.pop();
Q.push(temp);
}
QQ.push(Q.top()); // 肥耗子进队列，等下一轮处理
Q.pop();
while(!Q.empty()) {
mouse temp = Q.top();
Q.pop();
mice[temp.sequence].rank = rank;
}
}
cur = circles; // 筛出几只肥耗子，下一轮就要处理几只
}
mice[QQ.front().sequence].rank = 1; // 要处理的耗子只剩一只，那就是rank 1
sort(mice,mice+p,icmp);
for(int i = 0; i < p; ++i) {
// printf("mice[%d]=%d,rank=%d\n",i,mice[i].weight,mice[i].rank);
cout << mice[i].rank << ((i == p-1)?"\n":" ");
}
}
编辑于 2020-01-22 13:16:45
回复(0)
这个题目的意思太绕了，本意就是按给定的序列每ng个数字毕竟比较大小，大的进行下一轮，小的直接给出排名，
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
struct node {
int i,index,weight, rank;//index是在数组中的索引，i是在为比赛选手号码
node() {}
node(int i,int w, int r) :index(i),weight(w), rank(r) {}
}maxNode;
bool com(node a,node b) {
return a.i < b.i;
}
int main() {
int np = 0, ng = 0, index = 0,cnt = 0,group = 0,maxWei = 0;//np为总的竞赛人员个数，ng为每组个数,组的个数
cin >> np >> ng;
vector<node> p(np);
vector<int> num(np);
queue<node> q;
for (int i = 0, j = 0; i < np; i++) {//每个人员的初始化重量
scanf("%d", &j);
num[i] = j;
}
for (int i = 0, j = 0; i < np; i++) {//比赛顺序依次进队列
scanf("%d", &j);
p[i].i = j;
p[i].index = i;
p[i].weight = num[j];
}
for (int i = 0, j = 0; i < np; i++) {
q.push(p[i]);
}
while (!q.empty()) {
int size = q.size();
if (size == 1) {
node temp = q.front();
p[temp.index].rank = 1;
break;
}
group = size / ng;
if (size % ng != 0)group++;
for (int i = 0; i < size; i++) {
node temp = q.front();//临时接受，用于比较最大的
p[temp.index].rank = group + 1;
q.pop();
cnt++;
if (temp.weight > maxWei) {//更新最重的老鼠
maxWei = temp.weight;
maxNode = temp;
}
if (cnt == ng || i == size - 1) {//当计算到ng个老鼠的时候或者到达结尾的时候
q.push(maxNode);
cnt = 0;//计数器置0
maxWei = 0;//重置最大重量的老鼠
}
}
}
sort(p.begin(),p.end(),com);
int flag = 0;
for (int i = 0; i < p.size(); i++) {
printf("%d",p[i].rank);
if (i != p.size() - 1)printf(" ");
flag = 1;
}
if (!flag)printf("None");
cout << endl;
system("pause");
return 0;
}
编辑于 2019-10-26 10:47:17
回复(0)
import math import sys for s in sys.stdin: n,k=[int(x) for x in s.split()] r=[[int(t),i,-1]for i,t in enumerate(input().split())] p=[int(x) for x in input().split()] while True: t=0 p1=[[] for i in range(math.ceil(len(p)/k))] p2=p for i in range(len(p)): if i//k==t: p1[t].append(p[i]) if i%k==k-1: t+=1 p=[] for s in p1: p.append(max([r[i] for i in s])[1]) for i in p2: if i not in p: r[i][2]=len(p)+1 if len(p)==1: r[p[0]][2]=1 break s='' for i in range(n-1): s+=str(r[i][2]) s+=' ' s+=str(r[-1][2]) print(s) 这题的难点在于理解题意，一开始我很不能理解为什么比赛4轮，排名中会出现5 后来才明白排名是晋级人数+1 就像学校分数排名，有两个人分数一样排第二名，那么之后的人就排第四名了
发表于 2019-09-12 11:11:15
回复(0)
#include <bits/stdc++.h>
using namespace std;
unordered_map <int, int> mp, mp1;
int total, num, all = 0;
int weight[1001];
vector<int> v, tmp;
int main()
{ cin >> total >> num;
for (int i = 0; i < total; i++)
cin >> weight[i];
for (int i = 0; i < total; i++)
{ int k;
cin >> k;
v.push_back(k);
}
int i = 0, max_weight = -1, k = -1;
while(1)
{ int cnt = 0;
for (i = 0; i < v.size(); i++)
{ mp[v[i]] = 0;
if (weight[v[i]] > max_weight)
{ max_weight = weight[v[i]];
k = v[i];
}
if ((i + 1) % num == 0)
{ mp[k] = -1;
tmp.push_back(k);
max_weight = -1;
k = -1;
}
}
if (i % num != 0)
{ mp[k] = -1;
tmp.push_back(k);
}
// for(int i = 0; i < tmp.size(); i++)
// cout << tmp[i] << " ";
// cout << endl;
for(int i = 0; i < v.size(); i++)
if (mp[v[i]] != -1 )
{ mp[v[i]] = tmp.size() + 1;
all++;
}
if (tmp.size() == 1)
{ mp[tmp[0]] = 1;
break;
}
max_weight = -1; k = -1;
v = tmp; tmp.clear();
}
for(int i = 0; i < total; i++)
{ if (i != 0)
cout << " ";
cout << mp[i];
}
return 0;
}
发表于 2019-08-25 13:49:36
回复(0)
#include <queue>
#include <iostream>
using namespace std;
#define maxn 1010
struct mouse{ //老鼠结构体，质量与排名
int weight,rank;
}mouse[maxn];
int main(){
int np,ng,squ; //一共np个老鼠，每组有ng一起比赛
queue<int> q;
cin>>np>>ng;
for(int i=0;i<np;i++)
cin>>mouse[i].weight;
for(int i=0;i<np;i++){ //按题目给出的序号顺序入队
cin>>squ;
q.push(squ);
}
int temp=np,group; //temp为本轮有多少只老鼠参加比赛，group为组数
while(q.size()!=1){
if(temp%ng==0) group=temp/ng; //计算本轮有多少组
else group=temp/ng+1;
for(int i=0;i<group;i++){ //枚举每一组，选出该组优胜的老鼠
int maxm=q.front(); //maxm即该组最肥的老鼠编号
for(int j=0;j<ng;j++){
if(j>=temp-i*ng) break;//最后一组老鼠个数不足ng，即时退出循环
if(mouse[q.front()].weight>mouse[maxm].weight)
maxm=q.front();
mouse[q.front()].rank=group+1; //本轮输掉的老鼠排名即是本轮晋级的老鼠个数（一组一只，也即组数）加1
q.pop(); //出队
}
q.push(maxm); //让本组优胜的老鼠入队继续下一轮
}
temp=group; //下一轮参加比赛的老鼠即是本轮的组数（一组一只）
}
mouse[q.front()].rank=1; //队列剩下一只老鼠时，便是冠军，排名第一
cout<<mouse[0].rank;
for(int i=1;i<np;i++)
cout<<" "<<mouse[i].rank; //注意空格
return 0;
}
发表于 2019-01-07 16:07:42
回复(0)
问题信息
难度：
24条回答
8收藏
7574浏览
通过挑战的用户
-
2023-03-14 20:59:55
-
2023-03-13 17:25:27 -
2023-03-11 13:37:54
-
2023-02-26 16:25:32 -
2023-02-24 14:39:16
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
