新手自己建设一个网站,折腾wordpress,帮助中心网站源码,手机软件开发公司简介传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。
传送带上的第 i 个包裹的重量为 weights[i]。每一天#xff0c;我们都会按给出重量#xff08;weights#xff09;的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
返回能在 days 天内将…传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。
传送带上的第 i 个包裹的重量为 weights[i]。每一天我们都会按给出重量weights的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
返回能在 days 天内将传送带上的所有包裹送达的船的最低运载能力。 示例 1
输入weights [1,2,3,4,5,6,7,8,9,10], days 5
输出15
解释
船舶最低载重 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 [3,2,2,4,1,4], days 3
输出6
解释
船舶最低载重 6 就能够在 3 天内送达所有包裹如下所示
第 1 天3, 2
第 2 天2, 4
第 3 天1, 4示例 3
输入weights [1,2,3,1,1], days 4
输出3
解释
第 1 天1
第 2 天2
第 3 天3
第 4 天1, 1提示
1 days weights.length 5 * 1041 weights[i] 500 int canShip(vectorint weights, int k) { int cur 0; int retDays 0; while (cur weights.size()) { int sumTmp weights[cur]; if (cur 1 weights.size() sumTmp weights[cur1]k) { while (cur 1 weights.size() sumTmp weights[cur 1] k) { sumTmp weights[cur1]; cur; } } retDays; cur; } return retDays; } int shipWithinDays(vectorint weights, int days) { int avg 0, maxWei 0; int sumWei 0; for (int i 0; i weights.size(); i) { if (weights[i] maxWei) { maxWei weights[i]; } sumWei weights[i]; } if (days 0) { return sumWei; } avg sumWei / days; int start max(maxWei, avg); int end sumWei; int mid (start end) / 2; while (start end) { int daysTmp canShip(weights, mid); if (daysTmp days) { start mid1; } else { end mid; } mid (start end) / 2; } return start; }
