2604：吃掉所有谷子的最短时间（★★）

力扣第 2604 题

题目

一条线上有 n 只母鸡和 m 颗谷子。给定两个整数数组 hens 和 grains ，它们的大小分别为 n 和 m ，表示母鸡和谷子的初始位置。

如果一只母鸡和一颗谷子在同一个位置，那么这只母鸡可以吃掉这颗谷子。吃掉一颗谷子的时间可以忽略不计。一只母鸡也可以吃掉多颗谷子。

在 1 秒钟内，一只母鸡可以向左或向右移动 1 个单位。母鸡可以同时且独立地移动。

如果母鸡行动得当，返回吃掉所有谷子的 最短 时间。

示例 1 ：

输入：hens = [3,6,7], grains = [2,4,7,9]
输出：2
解释：
母鸡吃掉所有谷子的一种方法如下：
- 第一只母鸡在 1 秒钟内吃掉位置 2 处的谷子。
- 第二只母鸡在 2 秒钟内吃掉位置 4 处的谷子。
- 第三只母鸡在 2 秒钟内吃掉位置 7 和 9 处的谷子。
所以，需要的最长时间为2秒。
可以证明，在2秒钟之前，母鸡不能吃掉所有谷子。

示例 2 ：

输入：hens = [4,6,109,111,213,215], grains = [5,110,214]
输出：1
解释：
母鸡吃掉所有谷子的一种方法如下：
- 第一只母鸡在 1 秒钟内吃掉位置 5 处的谷子。
- 第四只母鸡在 1 秒钟内吃掉位置 110 处的谷子。
- 第六只母鸡在 1 秒钟内吃掉位置 214 处的谷子。
- 其他母鸡不动。
所以，需要的最长时间为 1 秒。

提示：

• 1 <= hens.length, grains.length <= 2*104
• 0 <= hens[i], grains[j] <= 109

相似问题：

• 0668：乘法表中第k小的数

分析

• 二分找最小满足的时间 x
• 先将两个数组都排序
• 固定 x，遍历每个母鸡，计算能吃到的最右边的谷子位置即可
• 计算位置类似于 2106

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def minimumTime(self, hens: List[int], grains: List[int]) -> int:
        def cal(a,b,c):
            return min(abs(a-b),abs(a-c))+c-b

        def check(x):
            i = 0
            for a in hens:
                j = i
                while j<m and cal(a,grains[i],grains[j])<=x:
                    j += 1
                i = j
            return i==m
        
        n,m = len(hens),len(grains)
        hens.sort()
        grains.sort()
        ma = cal(hens[0],grains[0],grains[-1])
        return bisect_left(range(ma),True,key=check)

859 ms