Readme

2616.Minimize-the-Maximum-Difference-of-Pairs

我们首先容易想到的是将数组排序，这样我们选择的pairs必然都是相邻的元素。任何跳跃选择的pair都必然不会是最优解。接下来我们该如何选择这些pairs呢？此时陷入了困难。我们并不能贪心地找相邻最短的pair，比如这个例子：1 3 4 6，我们优先取{3,4}之后，剩下的{1,6}的差距更大了。

在正面突破没有思路的时候，不妨试一试反向的“猜答案”。二分搜值在这里恰好是适用的。假设最大间距是x，那么当x越大时，我们就越容易找p对符合条件的pairs（比如当x是无穷大时，pairs可以随意挑）；反之当x越小时，就越不容易找到p对符合条件的pairs。以此不断调整x的大小，直至收敛。

于是接下来我们就考虑，假设最大间距是x，那么我们如何判定能否找到p对符合条件的pairs呢？为了尽量找到多的pairs，我们必然从小到大把这些元素都看一遍，尽量不浪费。假设最小的四个元素分别是abcd，并且他们彼此之间的间距都小于x，那么我们是否应该取a和b呢？如果取的话，那么可能带来的顾虑就是b就失去了和c配对的机会。不过这个顾虑是不必要的：如果我们选择了b和c，那么同样构造了一对，但a就白白浪费了。即使你可以将a与d配对且间距也小于x，那么也违背了我们之前的直觉，“我们永远只会取相邻的元素配对”。事实上(a,b)(c,d)的方案肯定是优于(b,c)(a,d)的。所以我们的结论就是，如果最小元素和它相邻元素的间距小于x，那么就贪心地配对；否则最小元素只能放弃。依次类推从小到大处理每一个元素，就可以知道我们最多能搞出多少个配对。