1056 Mice and Rice

本文主要是介绍1056 Mice and Rice，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给定一组选手，按一定顺序将这些选手进行分组竞赛，每组的最大值为优胜者，进入下一轮分组再进行竞赛，直到选出最大值。然后输出每个选手的rank。

坑点：每个选手的rank为该轮竞赛选出的优胜者数+1！！而不应该根据该选手是在第几轮淘汰算的！因为肯定比优胜者的rank低嘛。我阅读理解确实不太好，于是成功浪费两小时。

思路：可以用队列模拟选手顺序，每次取出组数个选手(不足则全部取出)，然后将优胜者放入下一轮队列中，淘汰者记录下来，最后将淘汰者的rank标记为优胜者数+1。

#include<bits/stdc++.h>
using namespace std;struct node{int val;int rank;
};
node p[1010];
queue<int>q;
int n,m;
int main(){cin>>n>>m;for(int i=0;i<n;i++){cin>>p[i].val;}for(int i=0;i<n;i++){int a;cin>>a;q.push(a);}while(q.size()>1){queue<int>next;queue<int>loser;while(q.size()){int k=min(m,(int)q.size());vector<int>temp;while(k--){int f=q.front();q.pop();temp.push_back(f);}int mx=-1,pos;for(auto x:temp){if(mx<p[x].val){mx=p[x].val;pos=x;}}for(auto x:temp){if(x!=pos){loser.push(x);}}next.push(pos);// cout<<pos<<' ';}while(loser.size()){int f=loser.front();loser.pop();p[f].rank=next.size()+1;}q=next;}p[q.front()].rank=1;int flag=0;for(int i=0;i<n;i++){if(flag)cout<<' ';cout<<p[i].rank;flag=1;}
}

这篇关于1056 Mice and Rice的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---