列表

详情

1889. 装包裹的最小浪费空间

给你 n 个包裹，你需要把它们装在箱子里，每个箱子装一个包裹。总共有 m 个供应商提供 不同尺寸 的箱子（每个规格都有无数个箱子）。如果一个包裹的尺寸 小于等于 一个箱子的尺寸，那么这个包裹就可以放入这个箱子之中。

包裹的尺寸用一个整数数组 packages 表示，其中 packages[i] 是第 i 个包裹的尺寸。供应商用二维数组 boxes 表示，其中 boxes[j] 是第 j 个供应商提供的所有箱子尺寸的数组。

你想要选择 一个供应商 并只使用该供应商提供的箱子，使得 总浪费空间最小 。对于每个装了包裹的箱子，我们定义 浪费的 空间等于 箱子的尺寸 - 包裹的尺寸 。总浪费空间 为 所有 箱子中浪费空间的总和。

请你选择 最优 箱子供应商，使得 总浪费空间最小 。如果 无法 将所有包裹放入箱子中，请你返回 -1 。由于答案可能会 很大 ，请返回它对 109 + 7 取余 的结果。

 

示例 1：

输入：packages = [2,3,5], boxes = [[4,8],[2,8]]
输出：6
解释：选择第一个供应商最优，用两个尺寸为 4 的箱子和一个尺寸为 8 的箱子。
总浪费空间为 (4-2) + (4-3) + (8-5) = 6 。

示例 2：

输入：packages = [2,3,5], boxes = [[1,4],[2,3],[3,4]]
输出：-1
解释：没有箱子能装下尺寸为 5 的包裹。

示例 3：

输入：packages = [3,5,8,10,11,12], boxes = [[12],[11,9],[10,5,14]]
输出：9
解释：选择第三个供应商最优，用两个尺寸为 5 的箱子，两个尺寸为 10 的箱子和两个尺寸为 14 的箱子。
总浪费空间为 (5-3) + (5-5) + (10-8) + (10-10) + (14-11) + (14-12) = 9 。

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: int minWastedSpace(vector<int>& packages, vector<vector<int>>& boxes) { } };

java 解法, 执行用时: 38 ms, 内存消耗: 67.3 MB, 提交时间: 2023-07-23 11:26:43 

class Solution {
    public int minWastedSpace(int[] packages, int[][] boxes) {
        int n = packages.length;
        Arrays.sort(packages);
        long[] preSum = new long[n + 1];
        for (int i = 0; i < n; ++i) {
            preSum[i + 1] = preSum[i] + packages[i];
        }

        long res = Long.MAX_VALUE;
        for (int[] box : boxes) {
            Arrays.sort(box);
            if (packages[n - 1] > box[box.length - 1]) {
                continue;
            }
            long t = 0;
            int low = 0;
            for (int b : box) {
                int idx = searchRight(packages, b, low);
                // 这里需要手动转 long
                t += ((idx - low) * (long) b - (preSum[idx] - preSum[low]));
                low = idx;
            }
            res = Math.min(res, t);
        }
        return res == Long.MAX_VALUE ? -1 : (int) (res % 1000000007);
    }

    private int searchRight(int[] packages, int target, int low) {
        int high = packages.length;
        while (low < high) {
            int mid = (low + high) >> 1;
            if (packages[mid] <= target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}

cpp 解法, 执行用时: 292 ms, 内存消耗: 113.3 MB, 提交时间: 2023-07-23 11:25:21 

class Solution {
private:
    using LL = long long;

    static constexpr int MOD = 1000000007;

public:
    int minWastedSpace(vector<int>& packages, vector<vector<int>>& boxes) {
        int n = packages.size();
        sort(packages.begin(), packages.end());

        // 计算数组 packages 的前缀和
        vector<LL> pre(n + 1);
        for (int i = 1; i <= n; ++i) {
            pre[i] = pre[i - 1] + packages[i - 1];
        }

        // 辅助函数，通过前缀和数组，得到数组 packages[left..right] 的和
        auto get = [&](int left, int right) {
            return pre[right + 1] - pre[left];
        };

        LL ans = LLONG_MAX;
        for (auto& box: boxes) {
            sort(box.begin(), box.end());
            // 小优化，如果最大包裹的尺寸大于最大箱子的尺寸，那么一定不满足，直接跳过
            if (packages.back() > box.back()) {
                continue;
            }

            // 初始化指针 pt，它指向还未被放入箱子的第一个包裹
            auto pt = packages.begin();
            // 总浪费空间
            LL total = 0;

            for (int y: box) {
                // 小优化，如果当前箱子 y 的尺寸小于 pt 指向的包裹，那么无需进行二分查找
                if (y < *pt) {
                    continue;
                }
                
                // pt'
                auto pt_next = prev(upper_bound(pt, packages.end(), y));
                
                total += (LL)(pt_next - pt + 1) * y - get(pt - packages.begin(), pt_next - packages.begin());
                pt = next(pt_next);
                // 小优化，如果所有包裹都已经被放入箱子，可以提前退出
                if (pt == packages.end()) {
                    break;
                }
            }
            ans = min(ans, total);
        }

        return (ans == LLONG_MAX ? -1 : ans % MOD);
    }
};

python3 解法, 执行用时: 316 ms, 内存消耗: 36.1 MB, 提交时间: 2023-07-23 11:24:53 

class Solution:
    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:
        MOD = 10**9 + 7
        
        packages.sort()
        # 计算数组 packages 的前缀和
        pre = list(accumulate(packages, initial=0))

        # 辅助函数，通过前缀和数组，得到数组 packages[left..right] 的和
        get = lambda left, right: pre[right + 1] - pre[left]
        
        ans = float("inf")
        for box in boxes:
            box.sort()
            # 小优化，如果最大包裹的尺寸大于最大箱子的尺寸，那么一定不满足，直接跳过
            if packages[-1] > box[-1]:
                continue

            # 初始化指针 pt，它指向还未被放入箱子的第一个包裹
            pt = 0
            # 总浪费空间
            total = 0

            for y in box:
                # 小优化，如果当前箱子 y 的尺寸小于 pt 指向的包裹，那么无需进行二分查找
                if y < packages[pt]:
                    continue
                
                # pt'
                pt_next = bisect_right(packages, y, pt) - 1
                
                total += (pt_next - pt + 1) * y - get(pt, pt_next)
                pt = pt_next + 1
                # 小优化，如果所有包裹都已经被放入箱子，可以提前退出
                if pt == len(packages):
                    break
            
            ans = min(ans, total)

        return -1 if ans == float("inf") else ans % MOD

golang 解法, 执行用时: 248 ms, 内存消耗: 13.2 MB, 提交时间: 2023-07-23 11:23:28 

// 由于包裹的尺寸之和是固定的，因此目标转换为最小化箱子的尺寸之和。
// 将包裹按尺寸排序后，按照箱子尺寸划分包裹，使得每个包裹都装入能装该包裹的最小的箱子。
// 这种贪心策略能使箱子的尺寸总和尽可能地小。
func minWastedSpace(a []int, boxes [][]int) int {
	sort.Ints(a) // 将包裹按尺寸排序，方便后面按照箱子尺寸划分包裹
	ans := math.MaxInt64
	for _, box := range boxes {
		sort.Ints(box)
		if box[len(box)-1] < a[len(a)-1] { // 最大的箱子不够装最大的包裹
			continue
		}
		res, l := 0, 0
		for _, v := range box {
			// 划分包裹：当前箱子 v 可以装入下标在 [l, r) 区间内的包裹
			r := sort.SearchInts(a, v+1)
			res += (r - l) * v // 统计箱子尺寸之和
			l = r
		}
		ans = min(ans, res)
	}
	if ans < math.MaxInt64 {
		for _, v := range a {
			ans -= v // 减去每个包裹尺寸
		}
		return ans % (1e9 + 7)
	}
	return -1
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

上一题

© 2024 leetcode.cn