CF431E Chemistry Experiment 题解
十年 OI 一场空，不开 long long 见祖宗。
一个 long long 调了我半个小时……
思路很好想，线段树上二分。怎么想出来的呢？众所周知，水银 和水
是不互溶的，而且水银的密度远大于水，所以水会漂在水银的上方。现在我们要让加水的试管的最大高度尽可能小，从这里可以推导出一个非常显而易见的结论：
最优方案中最后所有有水的试管的液面高度一定是相同的，否则不是最优方案。
可以用反证法证明：
若此情况不是最有情况，则一定有另外一种情况比这种情况更优。
假设最优情况中最低试管的液面高度为 ，最高试管的液面高度是
，且
。
我们不妨设 。那么我们可以把最高试管中的水倒一点到最低试管中，使得
变小，由此得到一个更优的情况。此结论与此情况是最优情况的假设矛盾。故结论得证。
接着，我们看到这个题目的表述非常像二分啊。（那就试试）
它有没有单调性呢？显然有的。
上二分！然后用权值线段树维护一下就没了……
Code:
