题目
1056 Mice and Rice（25 分）
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 N
P
programmers. Then every N
G
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 N
G
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.
Input Specification:
Each input file contains one test case. For each case, the first line contains 2 positive integers: N
P
and N
G
(≤1000), the number of programmers and the maximum number of mice in a group, respectively. If there are less than N
G
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 N
P
distinct non-negative numbers W
i
(i=0,⋯,N
P
−1) where each W
i
is the weight of the i-th mouse respectively. The third line gives the initial playing order which is a permutation of 0,⋯,N
P
−1 (assume that the programmers are numbered from 0 to N
P
−1). All the numbers in a line are separated by a space.
Output Specification:
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.
Sample Input:
11 3
25 18 0 46 37 3 19 22 57 56 10
6 0 8 7 10 5 9 1 4 2 3
Sample Output:
5 5 5 2 5 5 5 3 1 3 5
题解
一开始我连题目都不是很懂的。首先难点在理解排名这，为什么很多个5，没有4这种疑问。其实是被淘汰的排名并列了。每次晋级者的名次都是晋级的人数，直到晋级人数为1。
然后是怎样一组组比较的呢？第二排是所有老鼠，你可以想象是0号到10号的重量。而第三排就是要揪出第6只，第0只，第8只这样一组，然后第7，10，5一组这样进行比较。剩下不足一组3个的就两个一组。每次每组一只晋级。最后一组只有两只，获胜的就以逸待劳，一眼就看出来它是第2名啦。
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
//每一轮间，淘汰者们的名次等于幸存人数+1；
struct node{
int weight,index,index0,rank;
};
bool cmp(node a,node b){
return a.index0<b.index0;
}
int main(){
int np,ng,temp;
scanf("%d %d",&np,&ng);
vector<int> w(np);
vector<node> v(np);//比较过程中的节点
for(int i=0;i<np;i++){
scanf("%d",&w[i]);
}
for(int i=0;i<np;i++){
scanf("%d",&temp);
v[i].weight=w[temp];
v[i].index=i;//，把序号为6的放在了第一位，比较过程用的下标
v[i].index0=temp;//原来的下标，要输出的开始下标
}
queue<node>q;
for(int i=0;i<np;i++){
q.push(v[i]);
}
while(!q.empty()){
int size=q.size();
//先考虑最后的极端情况，只剩一个
if(size==1){
node last=q.front();
v[last.index].rank=1;
break;
}
int group=size/ng;
if(size%ng!=0){
group+=1;
}
node maxnode;
int maxn=-1,cnt=0;//maxn用于比较重量
for(int i=0;i<size;i++){
//这个for循环结果是：过完了第一波，剩下每组最大的那个在queue里
node last=q.front();
v[last.index].rank=group+1;//排定名次后吐出该点
q.pop();//先出来先进行比较，cnt+1
cnt++;
if(last.weight>maxn){
maxn=last.weight;
maxnode=last;
}//先估摸好最大的
if(cnt==ng||i==size-1){
//凑够一组或者到了最后
cnt=0;//一组比完了
maxn=-1;//进入新的一组对比
q.push(maxnode);//与之前的maxnode比
}
}
}
sort(v.begin(),v.end(),cmp);
for(int i=0;i<np;i++){
if(i!=0) printf(" ");
printf("%d",v[i].rank);
}
return 0;
} 这里的代码是从柳神那边学来的，完全理解了并加上注释才敢发出来。我于昨晚11点多，支付宝给她打了一块钱的赏试试水，结果没有上打赏名单额。
一开始是非完全正确的，因为自己写得时候局部变量cnt没有初始化为0。一般全局变量可不用，但局部变量一定要初始化（可能这句不完全正确）。