胥口镇
今天去富阳介绍智慧小镇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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

package solution;

import java.util.*;
import java.math.*;

class solution {
	public int shipWithinDays(int[] weights, int D) {
		int n = weights.length;
		int max = 0;
		int result = 0;
		for (int i = 0; i < n; i++) {
			max = max + weights[i];
		}
		while (result < max) {
			int s = (max + result) / 2;
			int z = s;
			int group = 1;
			for (int i = 0; i < n; i++) {
				if (z >= weights[i])
					z = z - weights[i];
				else {
					group++;
					z = s - weights[i];
				}
			}
			if (group <= D)
				max = s;
			else
				result = s + 1;
		}
		for (int i = 0; i < n; i++) {
			if (result < weights[i])
				result = weights[i];
		}
		return result;
    }
    
	public static void main(String[] args) {
		solution s = new solution();
		int[] b = { 3, 2, 2, 4, 1, 4 };
		int a = 3;
		System.out.print(s.shipWithinDays(b, a));
	}
}