「清华集训2016」汽水-二分+点分治

发布于 8 天前  32 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「清华集训2016」汽水-二分+点分治

Description

给定一棵树,有边权。

找到一条路径,使得经过的平均边权与$k$最接近。

$n \leq 50000,5s$

Solution

二分答案。设当前二分值为$p$,一条路径满足条件当且仅当

$$-p \leq \frac{\sum(w-k)}{len}\leq p$$

把边权减去$k$,移项得$-len \times p\leq\sum w\leq len\times p$

把条件拆成两条

$$-len \times p\leq\sum w<0$$
$$0\leq\sum w\leq len\times p$$

分开统计小于$0$的路径与大于等于$0$的路径,然后就可以点分治直接做了。

时间复杂度$O(nlog^2n)$,所以这题似乎可以开到$100000$,$1s$?

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「清华集训2016」汽水-二分+点分治


或许前方只有...伸手不见五指的夜路,即使如此,我还是要充满信心、继续向前, 相信星星的光芒...多少会照亮前方的道路,走吧!我们踏上旅程吧!