网站建设优化安徽推广平台app

数组的每个元素代表每个货物的重量，注意这个货物是有先后顺序的，先来的要先运输，所以不能改变这些元素的顺序。
要days天内把这些货物全部运输出去，问所需船的最小载重量。

思路：

数组内数字顺序不能变，就相当于拿days-1个隔板，把数组隔成days个部分，
每部分求和，这些和的最小值就是最小载重量。

暴力方法的话需要每固定一个隔板，然后调节剩下的隔板，
找出每个隔板内数字和的最小值，需要O(n^days)的复杂度。

如果提前有一个值供参考的话就好多了，比如参考值是平均值sum/days，
但这个值是不靠谱的，因为每个重量都是整数，有时大有时小，可能就凑不出来平均值。

那有没有一种方法提供一个参考的载重量，然后在实际过程中可调节呢。
比如说小于这个载重量就装船，超过了就加一天，第2天再装船，
最后发现天数超过了days，说明这个载重量不够，要加大。
反之载重量可以进一步缩小。

那每次要加大多少，减小多少呢，肯定不是1。

假如我们知道最大可能的载重量，比如是Integer的最大值，
然后在0和最大值之间找一个载重量，
能在days内装船就缩小，把最大载重量调节到现在值，
不能装就把最小载重量调节到现在的值，

这个是不是似曾相识的binary search.

最大载重量设为Integer的最大值是不是有点浪费？
观察一下，如果days内要运送完，把days-1个隔板平均放到数组中，
每部分货物的个数是n/days,
而且weight[i] <= 500, 那每个货物就按最大的500算，
所以最大载重量就是500 * (n/days+1).

    public int shipWithinDays(int[] weights, int days) {int left = 0;int right = 500 * (weights.length / days+1);while(left < right) {int mid = left + (right - left) / 2;if(canShip(weights, mid, days)) {right = mid;} else {left = mid + 1;}}return left;}boolean canShip(int[] weights, int capacity, int totalDays) {int sum = 0;int days = 1;for(int weight : weights) {if(weight > capacity) return false;sum += weight;if(sum > capacity){days ++;if(days > totalDays) return false;sum = weight;}}return true;}