题目传送门:Mice and Rice

题意

这题意我看了半天都不知道说的啥意思,先整理一下题意。

有n个老鼠,知道它们的重量,每次划分为若干组进行比赛,每组最多k个(不足k个则另计一组),给出最开始分组的顺序。每组比赛中只有一个最重的老鼠会晋级到下一轮继续比赛,而这组其他所有老鼠均被淘汰并给予它们一个名次。直到所有老鼠名次被确定时,结束比赛。

思路

能看懂题就能直接写代码了,用队列来模拟比较方便。

若每轮比赛划分为group组,则被淘汰的老鼠名次赋值为group+1,当队列大小为1时,给最后的赢家赋值,结束。

然后注意特判一下k=1,每个人就是一个组,每个人都是这个组的第1名,则1轮比赛就结束。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N=1010;
struct node
{
    int w;
    int order; // 初始分组顺序
    int pos; // 输入顺序
    int rk; // 最后的排名
}p[N];
queue<node>q,tq;
int main()
{
    ios::sync_with_stdio(false);
    int n,k; // n个人,k人一组
    cin>>n>>k;
    for(int i=0;i<n;i++)
        cin>>p[i].w;
    for(int i=0;i<n;i++)
    {
        cin>>p[i].order;
        p[i].pos=i;
    }
    if(k==1) // 特判k=1,每个人就是一个组,每个人都是这个组的第1名,则1轮比赛就结束
    {
        for(int i=0;i<n;i++)
            i==n-1?printf("1\n"):printf("1 ");
        return 0;
    }
    for(int i=0;i<n;i++)
        q.push(p[p[i].order]);
    node winner;
    while(q.size()>1)
    {
        int nows=q.size(); // 当前轮次总人数
        int group=nows/k; // 组数
        int rest=nows%k;
        if(rest!=0)group++; // 若最后剩下人数少于k,则另外加上最后一组
        for(int i=1;i<=group;i++)
        {
            // 第i组人数为num
            int num=k;
            if(i==group&&rest!=0)num=rest; // 一定要写 &&rest!=0  因为这里我wa了无数次
            int mx=-1;
            for(int j=1;j<=num;j++)
            {
                node tmp=q.front();q.pop();
                tq.push(tmp); // q的副本
                int w=tmp.w;
                if(w>mx)
                {
                    mx=w;
                    winner=tmp;
                }
            }
            q.push(winner); // 赢家进入下一轮
            for(int j=1;j<=num;j++)
            {
                node tmp=tq.front();tq.pop();
                if(tmp.pos!=winner.pos)
                {
                    p[tmp.pos].rk=group+1; // 给出局者赋值
                }
            }
        }
    }
    p[winner.pos].rk=1; // 给最后的冠军赋值
    for(int i=0;i<n;i++)
        i==n-1?printf("%d\n",p[i].rk):printf("%d ",p[i].rk);
    return 0;
}
/*
7 1
4 5 6 0 1 2 3
0 1 2 3 4 5 6
ans:1 1 1 1 1 1 1

11 1
25 18 0 46 37 3 19 22 57 56 10
6 0 8 7 10 5 9 1 4 2 3
ans:6 0 8 7 10 5 9 1 4 2 3

11 2
25 18 0 46 37 3 19 22 57 56 10
6 0 8 7 10 5 9 1 4 2 3
ans:4 7 7 2 4 7 7 7 1 3 4
*/