卧薪尝胆,厚积薄发。
Supercomputer
Date: Sat Mar 30 19:19:16 CST 2019
In Category:
NoCategory
Description:
$n$
个位置,每个位置容量为
$k$
。
$m$
个任务,每个任务要占据一个位置
$f_i$
,且要满足
$1\leqslant f_i\leqslant lim_i$
。支持
$q$
次动态添加任务,查询合法的
$k$
的最小值。
$1\leqslant n\leqslant 10^5,1\leqslant m\leqslant 10^5$
Solution:
首先可以直接二分图匹配做,但是会TLE,根据二分图的
$HALL$
定理我们可以得出
$sum[i]\leqslant i\times k$
,其中
$sum[i]=\sum_x [f_x\leqslant i]$
,那么对于每个位置都必须满足
$k\geqslant \big\lceil\frac{sum[i]}i\big\rceil$
,发现这个几乎不能用数据结构维护,那么我们可以考虑分块,最后的每一次添加都可以看成是对前缀和进行了一个后缀
$[v,n]$
加一的操作,那么对于
$v$
所在的块先不管维护什么反正我们可以暴力重构,考虑给一个区间整体加
$tag$
,那么每个数的变化是:
$$
\Big\lceil\frac{sum[i]+tag}i\Big\rceil=\Big\lceil tag\times\frac1i+\frac{sum[i]}i\Big\rceil
$$
那么每个位置
$i$
可以看成是一个斜率为
$\frac 1i$
,截距为
$\frac{sum[i]}i$
的直线,
$tag$
也就是
$x$
坐标单调递增,那么我们可以用单调栈对每个块求出凸包,然后每次打
$tag$
就可以让点在凸包上向右移动就可以找到最小值了。
Code:
没有代码
Copyright © 2020
wjh15101051
ღゝ◡╹)ノ♡