今天去富阳介绍智慧小镇ppt啦,跟镇长交谈中也收获了很多,我们做产品的需要结合小镇的特色产业进行定制,这样我们的产品才可以推广
目前乡镇政府需求是综合小镇的管理,推动小镇的特色产业,还有垃圾分类需求。于此同时,还需要解决乡村闲置资源和城市资本之间的对接,需要平台问题。
回到家后继续刷题~题目~~刷起来!!!!!
题目是在D天内送达包裹的能力;
传送带上有若干包裹,需要船在D天内送到另一个港口,每天船只能送一次,装载重量不会超过传达最大载运重量。求满足题意的最大船载重量的最小值。
示例1:
输入:weights = [1,2,3,4,5,6,7,8,9,10], D = 5
输出:15
解释1:
船舶最低载重 15 就能够在 5 天内送达所有包裹,如下所示:
第 1 天:1, 2, 3, 4, 5
第 2 天:6, 7
第 3 天:8
第 4 天:9
第 5 天:10
请注意,货物必须按照给定的顺序装运,因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。
示例2:
输入:weights = [1,2,3,1,1], D = 4
输出:3
解释2:
第 1 天:1
第 2 天:2
第 3 天:3
第 4 天:1, 1
题解:
一开始看到这道题,毫无头绪,询问了牛啵啵,他说可以用二分法来解决这道题,对于求解最大值最小,最小值最大等两个极限问题都可以用二分法来解决
这类解法称为二分答案转化为判定,在本题中,我们对船的载重量进行二分,以0和货物总重量作为边界,将其进行二分,得到中间值,再将包裹扔进去,看看需要多少天能运完,若送包裹天数小于等于规定天数D,说明该载重量不是最小值,将该值赋值给上边界,在对其进行二分,如此循环,最终上下边界重合,这就是我们所要求解的最大载运量的最小值。
需要注意的是,我们的最小值必须要大于单个包裹的重量,若求出的最小值小于单个包裹重量,我们就将单个包裹的最大重量作为最小值。
明天再深入研究二分算法哟~
代码如下:
1 |
|