ShanLunjiaJian的blog

ShanLunjiaJian的blog

仰天大笑出门去,我辈就是蓬蒿人

CF1299C Water Balance 题解

posted on 2021-01-31 13:55:59 | under 题解 |

我们考虑一个暴力做法 : 从小到大枚举一个$i$,然后枚举$j\geq i$使得

$$ \frac{\sum_{k=i}^j a_k}{j-i+1} $$

最小。我仿佛看到了一个经典模型,让我们换一换式子($sum$是前缀和) :

$$ \begin{aligned} &\frac{\sum_{k=i}^j a_k}{j-i+1}\\ =&\frac{sum_j-sum_{i-1}}{j-(i-1)} \end{aligned} $$

所以$j_1$优于$j_2$,当且仅当

$$ \begin{aligned} \frac{sum_{j_1}-sum_{i-1}}{j_1-(i-1)}&<\frac{sum_{j_2}-sum_{i-1}}{j_2-(i-1)}\\ \end{aligned} $$

然后就可以维护一个下凸壳了......等等,这是个2E啊,怎么会是斜率优化?

我们继续考虑这个操作是在干什么。在坐标系里面画出所有的$(i-1,sum_{i-1})$,然后你发现对$[l,r]$的一次操作就是把$l$和$r+1$这两个点连起来。要求字典序最小,相当于求下凸壳,所以我们单调栈一下就好了。非常奇妙。