BZOJ 2097 [Usaco2010 Dec]Exercise 奶牛健美操


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2097

题意:把树切 S 刀,最大直径最小。


显然二分答案,自底向上的贪心判定,若目前子树中存在比 mid 长的链,就切断它。

显然是最优的策略,但是我比较傻逼的考虑了一个问题:

切断一条链的过程肯定是贪心的切断最下面的 mid 的节点,此时是否可能存下这半条最长链剩下的部分和另外半条链加起来又成为了一条比 mid 长的链呢?

YY 了一下显然是不存在这种情况的,考虑证明:

设目前最长链(半条)链长为\(len_{fir}\),次长链链长\(len_{sec}\),则存在\(len_{fir}+len_{sec}>mid\) 使得我们必须切断它。

切断最长链后得到新链\(len_{new}=len_{fir}-mid\),此时若新链是某条比 mid 长的链的一部分,必可以和次长链构成它。即有:\(len_{new}+len_{sec}>mid\)

此时有\(len_{fir}+len_{sec}>2\cdot mid\),若成立,则必有\(len_{fir}>mid\),但是这样的话在考虑上一层时已经切断了这条链。

那么就可以了... 人要多傻才会去考虑这种东西... 这不是显然的吗

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 2097 [Usaco2010 Dec]Exercise 奶牛健美操


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , ,