题解：CF1619F Let's Play the Hat?

TCY1234567 · 2026-06-10 19:41:55 · 题解

题解

首先不难发现，大桌子一定有 n \bmod m 个。剩下的全是小桌子。

然后发现小桌子怎么排列完全不用管，所以我们只讨论大桌子的情况。

对于一个大桌子，我们要使 b_i 之差不大于 1，所以考虑贪心策略，用优先队列，每一次统计出 b_i，然后从优先队列里拿出较小的值，这样的话，每一次需要所有的 b_i 基本持平后才能继续增加最大值，直接维护即可。

代码

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int b,id;
    bool operator < (const node &x) const
    {
        return b>x.b;
    }
};
int cnt[200005];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m,k;
        scanf("%d%d%d",&n,&m,&k);
        for(int i=1;i<=n;i++) cnt[i] = 0; 
        int big = n%m;
        for(int i=1;i<=k;i++)
        {
            priority_queue<node> q;
            for(int j=1;j<=n;j++)
                q.push({cnt[j],j});
            for(int j=1;j<=big;j++)
            {
                printf("%d ",n/m+1);
                for(int k=1;k<=n/m+1;k++)
                {
                    auto x = q.top();
                    q.pop();
                    cnt[x.id]++;
                    printf("%d ",x.id);
                }
                puts("");
            }
            for(int j=1;j<=m-big;j++)
            {
                printf("%d ",n/m);
                for(int k=1;k<=n/m;k++)
                {
                    auto x = q.top();
                    q.pop();
                    printf("%d ",x.id);
                }
                puts("");
            }
        }
        puts("");
    }
}