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

原题链接

• 洛谷 P11523 [THUPC2025 初赛] 摊位分配

解题思路

序列 $u_i, \frac{u_i}{2}, \frac{u_i}{4}, \cdots, \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;
}