Gravatar
梦那边的原神
积分:1462
提交:150 / 270

Pro4268  [THUPC 2025 pre] 摊位分配

看到这个题的第一眼就气笑了,都 2026 年了,出题人企图让我在代码里用小数运算。

这给了我一个提示:说不定这个与众不同题其实就是要用一些与众不同的算法。

注意到分配最多摊位的社团与分配最少摊位的社团的摊位差不超过 $30$,因为对于任意 $i,j$,都有 $u_i\times 2^{30}>u_j$。

好的,我们先执行这样的操作若干轮:每次都给一个社团一个摊位,但需要保证 $m-n\ge 30n$。

什么,暴力模拟会 TLE,没事,我们模拟倍增的过程分配。

此时 $m$ 被缩小到 $31n$ 这个级别了,直接用堆模拟即可,时间复杂度 $O(n\log^2 V)$。

注意到 COGS 机子太垃圾被卡常了,只能把 $m$ 缩小到 $30n$ 这个级别了。

最劣解喜加一。


2026-01-30 20:30:20    
我有话要说
暂无人分享评论!