[USACO20OPEN] Social Distancing I B

1234567890sjx · 2023-12-24 16:58:20 · 题解

看到最小值最大，所以想到二分答案。

设当前二分的 D 值为 p，那么考虑计算出当前所有的差值，然后把两头奶牛贪心的插入到差值最大的地方即可。特殊的，有一种特殊情况是两头奶牛插入到了同一个地方，特判掉即可。

直接做即可。时间复杂度 O(n\log n)。