题解：P11523 [THUPC 2025 初赛] 摊位分配

· · 题解

解题思路

序列 u_i,\frac{u_i}{2},\frac{u_i}{4},\dots,\frac{u_i}{2^{H-1}} 是单调递减的，显然只有取到 \frac{u_i}{2^k} 后，才能取到 \frac{u_i}{2^{k+1}}。因此，可以维护一个大顶堆，初始时将每个社团的权值都放入堆中。

枚举每个格子，每次从大顶堆中取出权值最大的社团，将该格子分配给该社团，并将其权值减半后重新放回堆中。这种方法的时间复杂度为 O(H\log T)，还可能因浮点运算产生精度问题，无法通过此题。

考虑优化，注意到任意权值 u_i 都可以表示为 a_i\times 2^{n_i}，其中 1\leq a_i<2 且 n_i\in\mathbb{N}。当大顶堆中堆顶元素小于 2 时，堆内所有元素均位于区间 [1,2)。

此时有个很好的性质，即对于任意 a_i < a_j,k\in\mathbb{N}，满足：

\frac{a_i}{2^{k+1}}<\frac{a_j}{2^{k+1}}<\frac{a_i}{2^k}<\frac{a_j}{2^k}

设还剩 h 个待分配的格子，每个社团会先被分配 \left\lfloor\frac{h}{T}\right\rfloor 个格子，剩下的 h\bmod T 个格子将优先分配给权值 a_i 最大的 h\bmod T 个社团。

显然，对于每个 u_i，其 n_i\sim\log u_i，因此时间复杂度为 O(T\log u_i)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=100005;
struct Node
{
    int id,cnt;
    double val,st;
    bool operator<(const Node &rhs) const
    {
        if(val!=rhs.val)return val<rhs.val;
        if(cnt==0^rhs.cnt==0)return cnt;
        if(st!=rhs.st)return st<rhs.st;
        return id>rhs.id;
    }
}a[N];
int ans[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    cin>>n>>k;
    priority_queue<Node> q;
    for(int i=1;i<=n;i++)
    {
        double x;
        cin>>x;
        q.push({i,0,x,x});
    }
    while(!q.empty()&&k)
    {
        Node u=q.top();
        if(u.val<2)break;
        q.pop();
        u.cnt++;
        u.val/=2;
        q.push(u);
        k--;
    }
    while(!q.empty())
    {
        Node u=q.top();
        q.pop();
        a[u.id]=u;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
    {
        ans[a[i].id]=a[i].cnt+k/n+(i>n-k%n);
    }
    for(int i=1;i<=n;i++)
    {
        cout<<ans[i]<<' ';
    }
    return 0;
}