CF505E 题解
$\text{Description}$
给定 $n,m,k,p$,给定两个序列 $\{h_n\}$ 和 $\{a_n\}$,接下来你要执行 $m$ 轮操作:
- 进行 $k$ 次特殊操作,每次特殊操作可以选择一个数 $i\in[1,n]$,然后使得 $h_i\gets \max(h_i-p,0)$;
- 对于所有 $i\in[1,n]$,使得 $h_i\gets h_i+a_i$。
现在你需要使得最后 $\max\limits_{1\le i\le n}\{h_i\}$ 最小。
$\text{Solution}$
首先最小化最大值这种问题很容易让我们想到二分答案,于是我们将问题转换为:是否存在一种操作方式,使得最后所有 $h_i<H$。
然后发现这个 $h_i$ 必须是非负的,所以它会使得这个贪心过程比较困难。
考虑再进行一次转换:存在一个满足 $\forall i\in[1,n],h’_i\ge h_i$ 的序列 $\{h’_ n\}$ ,存在一种操作方式使得最终 $\forall i\in[1,n],h’_n=H$。为什么这个和上面的问题是等价的呢?我们找出不同点:$h’_i\ge h_i,(last)h’_i=H$,发现如果存在一种操作方式使得这个条件满足的话,那么将这个操作方式应用在 $\{h_n\}$ 上后,就一定有 $(last)h_i\le H$。
我们接着思考:如果存在一个满足条件的初始序列,经过一种操作方式后使得最终序列里的数都等于 $H$,那么我们将操作方式反过来做一遍(顺序相反,加变减,减变加),就可以得到一个满足条件的初始序列。那么我们又进行了一个转换:
给定一个序列 $\{h’_ n\}$,你需要执行 $m$ 轮操作:
- 将所有 $i\in[1,n]$ 都执行 $h’_i\gets h’_i-a_i$;
- 进行 $k$ 次特殊操作,每次特殊操作可以选择 $i\in [1,n]$,然后执行 $h’_i\gets h’_i+p$。
那么怎样一个操作方式是合法的呢?它需要满足任意时刻不存在一个 $i\in[1,n]$ 使得 $h’_i<0$,这是因为 $h_i$ 非负。除此之外,还要满足最后时刻 $\forall i\in[1,n]$,都有 $h’_i\ge h_i$。
考虑到若有一个 $i$ 满足 $H-m\cdot a_i\ge h_i$,由于 $h_i$ 非负,所以这个 $i$ 是永远满足条件的,不需要去管。
考虑这么一个贪心:我们每次优先选择最快要变为负数的 $i$,然后给它加 $p$。在此基础上,我们维护一个数被加了多少次 $p$,记之为 $c_i$,维护一个小根堆,其以最早变为负数的天数前一天为关键字($\lfloor\frac{(H+c_i)}{a_i}\rfloor$,注意 $h’_i$ 是可以为 $0$ 的)。每次特殊操作我们取堆顶进行一次特殊操作,然后判断其在经过这一次特殊操作后,是否可以再也不用特殊操作也能在最终满足 $h’_i\ge h_i$,若不是,则要将其再次插入堆中。最后只需判断堆是否为空即可。
几个细节需要注意,任何要取堆顶或弹出堆顶时候都要判断堆是否为空,还有判断其是否需要再次插入堆中时要记得加上 $c_i\cdot p$。
$\text{Code}$
1 |
|