首页 🍒LeetCode,🐶算法

题目

EySuLPMtl6.png

思路

船的承重一定是>=货物中最重的那个,<=所有货物的总重。
所以就可以采用二分法确定船的承重,假设船的承重为x,y天运完,if (y > D): x应该增加 else: x应该减少。y == D,x可以直接输出答案。

二分的区间为(货物中最重的, 货物的总重)
定义day为承重为mid时的天数,num为这一天已经已经放在船上的货物和。

每一天应该运送的货物应该在小于等于承重的情况下尽可能多的运送,所以当num + 今天的货物重量 > mid时今天能运送的货物就达到了上限。

class Solution {
public:
    int shipWithinDays(vector<int>& weights, int D) {
        int left = 0, right = 0;
        for (int w : weights) {
            left = max(left, w);
            right += w;
        }
        while (left < right) {
            int mid = (left + right) / 2;
            int day = 1, num = 0;
            for (int w : weights) {
                if (num + w > mid) {
                    day++;
                    num = 0;
                }
                num += w;
            }
            if (day > D) {
                left = mid + 1;
            }
            else {
                right = mid;
            }
        }
        return left;
    }
};



文章评论