网站建设结构设计方案,3000元做网站,影视小程序搭建,大良外贸网站设计数组的每个元素代表每个货物的重量#xff0c;注意这个货物是有先后顺序的#xff0c;先来的要先运输#xff0c;所以不能改变这些元素的顺序。 要days天内把这些货物全部运输出去#xff0c;问所需船的最小载重量。
思路#xff1a;
数组内数字顺序不能变#xff0c;就… 数组的每个元素代表每个货物的重量注意这个货物是有先后顺序的先来的要先运输所以不能改变这些元素的顺序。 要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/days1). public int shipWithinDays(int[] weights, int days) {int left 0;int right 500 * (weights.length / days1);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;}
