这样问题就变简单了,不过好像还是没有简单到哪里去(吧(?)
重洞可以不用架在城镇上的话,二分答案就可行了,所以对于一个 d ,我们要判断是否能够找到两个点,在这两个点建虫洞之后可以让任两点的最短距离都<=d.所以我们需要先知道虫洞应该要架在哪是最好的.
假设虫洞的左端点建在A,右端点建在B,所有城镇的最左城镇叫P,最右城镇叫Q,那么如果 AP + BQ < d ,就可以把 A 往右移,B 往左移,移到 AP + BQ = d 为止,而且他们移动的距离一样(也就是保持AB的中点固定,然后让A根B往内缩),可以证明调整之后的任两点之间的最短距离都不会变大,还有机会变小,所以这样是可行的.
而做到了这个结论后也可以不用二分答案了,直接用 lowerbound 就可以得到答案了.