求问leetcode 1011. Capacity To Ship Packages Within D Days怎么想到二分法？

感觉这道题和1335. Minimum Difficulty of a Job Schedule很像，自己的思路就是n^3的dp，完全没想到居然是用二分法解。请教地里的大神这道题里的什么信息能让人想到二分法呢？回复的都会加米！谢谢^^

北极兔兔鲨 发表于 2020-12-20 02:45
啊啊地里真的有好多大神！非常感谢你的回复，你说的单调性感觉很关键，毕竟二分法就是适用于单调性的问题 ...

嗯，对的。很多题目直接求比较复杂，我们知道解的范围，就可以通过二分来确定第一个满足条件的值。通常的问法比如满足某种条件的最大值最小之类的都可以尝试一下二分。

就是猜答案，然后在值域上具有某种单调性，因为每天运w的物品可行的话，任何大于w的容量都是可行的。也就是这里其实要找的就是可行的值域里面的最小值。即在w是可行，但是w-1不可行。我们验证是否可行就可以直接线性扫一遍。可以参考一下我之前写的一个二分查找的理解。
https://www.1point3acres.com/bbs/thread-660719-1-1.html

不知道小帅 发表于 2020-12-19 09:30:52
就是猜答案，然后在值域上具有某种单调性，因为每天运w的物品可行的话，任何大于w的容量都是可行的。也就是这里其实要找的就是可行的值域里面的最小值。即在w是可行，但是w-1不可行。我们验证是否可行就可以直

啊啊地里真的有好多大神！非常感谢你的回复，你说的单调性感觉很关键，毕竟二分法就是适用于单调性的问题。
因为“如果容量w可行，那么大于w的容量都可行”这个性质，把题目转换为找最小的可行的容量w。我觉得还有一个关键的性质是容量w是有范围的，就是从单个最大的物体体积到所有物体体积之和。这样就变成在一个范围中找一个满足某条件的最小值了，咩咩。

不知道小帅 发表于 2020-12-19 09:30:52
就是猜答案，然后在值域上具有某种单调性，因为每天运w的物品可行的话，任何大于w的容量都是可行的。也就是这里其实要找的就是可行的值域里面的最小值。即在w是可行，但是w-1不可行。我们验证是否可行就可以直

你的帖子我仔细看一下～