🐂 愤怒的牛 · 二分答案

农夫约翰有 N（2 ≤ N ≤ 100000）个隔间，排成一条直线，第 i 个隔间坐标是 x_i（0 ≤ x_i ≤ 10⁹）。他有 C（2 ≤ C ≤ N）头牛，牛因为离得太近而"愤怒"！约翰要把牛放进隔间，让相邻两头牛之间的最近距离越大越好。求这个最大的最近距离。

为什么能二分？答案（距离）的范围是 [1, 最大间距]。距离越大越难放下所有牛——距离 d 可行，那么比 d 小的都可行；d 不可行，比 d 大的都不可行。这种单调性，正是二分的灵魂！

check(x) 怎么验证？贪心！第 1 头牛放最左边的隔间，然后往后扫，能放就放（和上一头牛距离 ≥ x 就放下），最后看能不能放下 C 头牛。"能放就放"一定是最优的放法。

口诀：找解用 check！（二分查找比 a[mid] 和 t，二分答案比 check(mid) 行不行）