Aggressive Cows
谷仓里沿着一条直线排列着一些牛栏，stalls[i] 表示第 i 个牛栏的位置。所有位置都不相同，且没有特定的顺序。你必须把 k 头牛放进 k 个不同的牛栏里。牛靠得太近时会打架，所以你要尽可能拉开最近两头牛之间的距离。
返回任意两头牛之间最小距离可能达到的最大值。
函数
- stallsinteger-array
- 不同的摊位位置，顺序任意
- kinteger
- 要放置的奶牛数量
- 返回值integer
- 两头牛之间可能的最大最小距离
约束条件
2 ≤ stalls.length ≤ 50000 ≤ stalls[i] ≤ 109- 所有
stalls中的位置都不相同。 2 ≤ k ≤ stalls.length
示例
- 输入
- stalls = [10, 1, 7, 4, 15]k = 3
- 输出
- 6
- 解释
- 位于 1、7 和 15 的奶牛之间分别相隔 6 和 8。间隔为 7 不行：在 1 之后，下一头奶牛会放在 10，而 17 或更大的位置没有牛栏。
- 输入
- stalls = [9, 3, 20, 5]k = 4
- 输出
- 2
- 解释
- 4 头奶牛和 4 个牛棚意味着每个牛棚都有一头奶牛。排序后，牛棚的位置是 3、5、9 和 20，最近的两个位置是 3 和 5，相距 2。
- 输入
- stalls = [14, 2, 30, 22, 8]k = 2
- 输出
- 28
- 解释
- 两头牛分别站在队伍的两端是最好的。畜栏从 2 到 30，所以两头牛相距 28。
进阶
如果摊位围成一个圆，顺序中的最后一个摊位也与第一个摊位相邻，会有什么变化？
提示
逐个打开提示，每个都会多透露一点。
先把最佳答案放一放。如果有人给你一个间距
g，你能判断是否可以放下k头牛，并且任意两头牛之间的距离至少为g吗？对牛棚进行排序，然后从左向右放置奶牛，每头奶牛都放在第一个距离上一头奶牛至少
g的牛棚里。如果某个间距可行，那么所有更小的间距也都可行。在 1 和摊位间距除以
k-1的结果之间对g进行二分查找。保留贪心算法能够放置至少k头牛的最大间距。
题解
选定一个间距，然后问：是否能让 k 头牛站在牛栏里，并且任意两头牛之间的距离至少为这个间距？按顺序遍历排序后的牛栏，只需贪心遍历一遍就能得出答案。随着间距增大，答案会从“可以”变为“不可以”，而且只会变化一次，所以可以用二分查找找到最后一个“可以”的间距。
排序，然后依次尝试每个空档
结果正确，但无法在最大的测试中运行完毕
思路
对位置进行排序。距离最近的两头牛总是相邻的，因此当每对相邻的牛之间至少相隔 g 时，间距 g 就可行。
要测试一个间距，先把一头牛放在最左边的牛棚里，然后每次都在距离上一头牛至少 g 的牛棚里放一头牛。这种贪心放置方式能放下的牛最多，不会少于任何其他放置方式。把任何一种可行的放置方式从左边对齐：贪心放置的第 i 头牛都不会比该方式中的第 i 头牛更靠右，因此贪心方式能更早为下一头牛找到牛棚。
间距为 1 时总是可行的，所以尝试 g = 2, 3, ...，当放下的牛少于 k 头时，就在第一个这样的间距处停止。在第一个例子中，间距为 6 时能放下 3 头牛，间距为 7 时只能放下 2 头，因此答案是 6。
如果有两头牛，牛棚分别位于 0 和 10^9，那么需要对 5000 个牛棚遍历约 10^9 次，共 5 × 10^12 步。
算法
- 对位置进行排序。
- 编写检查间距
g的逻辑：一头牛放在pos[0]，然后在每个满足pos[i] - last ≥ g的牛棚放一头牛，并统计牛的数量。 - 从
gap = 1开始。 - 只要检查
gap + 1时能放下至少k头牛，就将gap加 1。 - 返回
gap。
def cowsPlaced(pos, gap):
count, last = 1, pos[0] # the first cow takes the leftmost stall
for p in pos[1:]:
if p - last >= gap:
count += 1
last = p
return count
def aggressiveCows(stalls, k):
pos = sorted(stalls)
gap = 1 # positions are distinct, so a gap of 1 always fits every cow
while cowsPlaced(pos, gap + 1) >= k:
gap += 1
return gap间隔上的二分查找
思路
每个间隔都至少为 g+1 的放置方案，其每个间隔也至少为 g，所以检查结果依次为“是，……，是，不，……，不”。二分查找可以找到最后一个“是”。
从始终可行的 lo = 1 开始，将 hi 设为跨度除以 k-1 后向下取整：k 头牛在跨度内会留下 k-1 个间隔，因此最小间隔不可能更大。检查通过时，将 lo = mid，所以 mid 必须向上取整；如果向下取整，lo = 5 且 hi = 6 时就会永远重复。
在第一个示例中，跨度为 14，且 k = 3，所以 hi = 7。间隔为 4 时通过，间隔为 6 时通过，间隔为 7 时失败，范围最终收敛到 6。
宽度为 10^9 的范围，大约经过 30 次检查就能收敛。每次检查 5000 个摊位，总共约需 150,000 步。
算法
- 对位置进行排序。
- 设置
lo = 1和hi = (pos[n-1] - pos[0]) / (k-1)，向下取整。 - 当
lo < hi时，取mid = lo + (hi - lo + 1) / 2。 - 如果在
mid处进行贪心检查后，至少能放置k头牛，就设置lo = mid；否则设置hi = mid - 1。 - 返回
lo。
def cowsPlaced(pos, gap):
count, last = 1, pos[0] # the first cow takes the leftmost stall
for p in pos[1:]:
if p - last >= gap:
count += 1
last = p
return count
def aggressiveCows(stalls, k):
pos = sorted(stalls)
lo = 1 # positions are distinct, so a gap of 1 always works
hi = (pos[-1] - pos[0]) // (k - 1) # k-1 gaps share the whole span
while lo < hi:
mid = lo + (hi - lo + 1) // 2 # round up so lo = mid always moves
if cowsPlaced(pos, mid) >= k:
lo = mid # mid fits, so the answer is mid or larger
else:
hi = mid - 1 # mid does not fit, so the answer is smaller
return lo
易错点和边界情况
- 跳过排序。对于未排序的
[10, 1, 7, 4, 15]，间距为 6 时，检查从 10 开始，后面没有间隔至少为 6 的牛栏，因此结果是 1 头牛。 - 当一轮循环中设置
lo = mid时，将mid向下取整。一旦hi = lo + 1，范围就不再缩小，循环永远不会结束。 - 检查牛的数量是否恰好等于
k。第一个示例中，间距为 1 时可以放下 5 头牛，超过了 3 头，但这个间距仍然可行；应检查count ≥ k。 - 将牛的数量从 0 开始计数。最左边牛栏里的牛也要计入，因此计数应从 1 开始。
常见问题3
Aggressive Cows 的时间复杂度是多少？
排序需要 O(n log n)，二分查找需要 O(n log D)，其中 D 是摊位跨度除以 k-1。除了排序后的副本，内存开销为 O(1)。
为什么第一头奶牛总是进入最左边的牛棚？
选择任意一种可行的摆放方式，把最左边的牛移到最左边的牛栏。这样只会让这头牛远离其他牛，因此不会缩短任何距离，而且总有一种最优摆放方式会用到最左边的牛栏。
如何识别答案上的二分查找？
题目要求找出某件事可行时的最大值或最小值。检查一个值比找出最优值容易得多，而且随着值增大，答案只会翻转一次。这里的值是间距，检查方法是贪心放置。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def aggressiveCows(stalls, k):
# 在这里写代码测试 #1
测试 #2
测试 #3
参数
stalls = [10, 1, 7, 4, 15] k = 3
预期输出
6