【IOI2016】捷径

题意:有一条\(n\)个点的链,每个点又连接了一个特殊点,每条边有一个距离。现在你可以在链上某两个点间连一条权值为\(c\)的边使得得到的基环外向树直径最小。

 

考虑二分答案。

令\(len_i\)为链上点到最左端点的距离(即\(l\)的前缀和),

假设二分出的答案为\(k\),那么要求存在一对点\(a,b\),使得对于所有的\(len_j-len_i+d_j+d_i>k(i<j)\),有\(|len_i-len_a|+|len_j-len_b|+d_i+d_j+c<=k\)。

绝对值不好处理,将绝对值分四种情况得到四个不等式,只要同时满足即可。

按照\(len_j+d_j\)的顺序枚举\(j\),那么对应的\(i\)在按照\(len_i-d_i\)排序的数组内一定是一段区间,且端点单调。只需要满足\(i<j\)即可。将二分下界设为最大的两个\(d\)的和即可保证\(i<=j\),再在查询的时候记录要求的值的次大值,如果最大值对应的位置正好是当前枚举的\(j\)那么用次大值更新答案。那么就能求出\(len_b+len_a\)以及\(len_b-len_a\)的范围。

于是枚举\(b\),对应的\(a\)也是一段区间。不断更新区间端点即可,次数也是\(O(n)\)的。如果区间不为空则有解。

说点什么

您将是第一位评论人!

提醒
wpDiscuz