Leetcode 2604. 吃掉所有谷子的最短时间
1.题目基本信息
1.1.题目描述
一条线上有 n 只母鸡和 m 颗谷子。给定两个整数数组 hens 和 grains ，它们的大小分别为 n 和 m ，表示母鸡和谷子的初始位置。
如果一只母鸡和一颗谷子在同一个位置，那么这只母鸡可以吃掉这颗谷子。吃掉一颗谷子的时间可以忽略不计。一只母鸡也可以吃掉多颗谷子。
在 1 秒钟内，一只母鸡可以向左或向右移动 1 个单位。母鸡可以同时且独立地移动。
如果母鸡行动得当，返回吃掉所有谷子的 最短 时间。
1.2.题目地址
https://leetcode.cn/problems/minimum-time-to-eat-all-grains/description/
2.解题方法
2.1.解题思路
二分查找。吃完谷子时间下限为0，上限为母鸡最大坐标+谷子最大坐标；对于二分检查的思路，不递减的枚举母鸡和谷子的位置，贪心的让谷子被最左边的母鸡吃掉，如果不能，则尝试让下一个母鸡吃掉，最后判断所有谷子能否被全部吃掉
时间复杂度：O((m+n)log(m+n)) （m和n分别为hens和grains的数组长度）
2.2.解题步骤
第一步，将谷子和母鸡位置进行升序排列
第二步，构建二分查找的检查函数
2.1.设计维护变量。i维护当前母鸡的指针，p维护当前谷子的指针，l和r维护时间t内当前母鸡能够吃掉谷子的最大范围
2.2.根据当前谷子、母鸡的位置更新l和r
2.3.判断当前的l和r范围内的谷子能否被当前的母鸡在时间t内吃完；如果能，则枚举下一颗谷子；如果不能，则枚举下一个母鸡，尝试吃掉当前谷子p
2.4.根据最终的谷子的指针p和总谷子数判断时间t内是否能够全部吃完所有谷子
第三步，二分查找主体；左闭右闭；红蓝染色：红色区域：时间t内不能全部吃完；蓝色区域：时间t内能全部吃完；left-1和right+1始终指向红色和蓝色区域，最终的left即为题解
3.解题代码
Python代码
class Solution:def minimumTime(self, hens: List[int], grains: List[int]) -> int:# 思路：二分查找。吃完谷子时间下限为0，上限为母鸡最大坐标+谷子最大坐标；对于二分检查的思路，不递减的枚举母鸡和谷子的位置，贪心的让谷子被最左边的母鸡吃掉，如果不能，则尝试让下一个母鸡吃掉，最后判断所有谷子能否被全部吃掉# 时间复杂度：O((m+n)log(m+n))# 第一步，将谷子和母鸡位置进行升序排列grains.sort()hens.sort()# 第二步，构建二分查找的检查函数def check(t:int) -> bool:# 2.1.设计维护变量。i维护当前母鸡的指针，p维护当前谷子的指针，l和r维护时间t内当前母鸡能够吃掉谷子的最大范围p = 0for i in range(len(hens)):l, r = 0, 0while p < len(grains):# 2.2.根据当前谷子、母鸡的位置更新l和rif grains[p] > hens[i]:r = max(r, grains[p] - hens[i])else:l = max(l, hens[i] - grains[p])# 2.3.判断当前的l和r范围内的谷子能否被当前的母鸡在时间t内吃完；如果能，则枚举下一颗谷子；如果不能，则枚举下一个母鸡，尝试吃掉当前谷子pif min(2 * l + r, 2 * r + l) <= t:p += 1else:break# 2.4.根据最终的谷子的指针p和总谷子数判断时间t内是否能够全部吃完所有谷子return p == len(grains)# 第三步，二分查找主体；左闭右闭；红蓝染色：红色区域：时间t内不能全部吃完；蓝色区域：时间t内能全部吃完；left-1和right+1始终指向红色和蓝色区域，最终的left即为题解left, right = 0, grains[-1] + hens[-1]while left <= right:mid = (right - left) // 2 + leftif not check(mid):left = mid + 1else:right = mid - 1return left4.执行结果
