跳转至

3492. 船上可以装载的最大集装箱数量

题目描述

给你一个正整数 n，表示船上的一个 n x n 的货物甲板。甲板上的每个单元格可以装载一个重量 恰好 为 w 的集装箱。

然而，如果将所有集装箱装载到甲板上，其总重量不能超过船的最大承载重量 maxWeight。

请返回可以装载到船上的 最大 集装箱数量。

 

示例 1：

输入： n = 2, w = 3, maxWeight = 15

输出： 4

解释：

甲板有 4 个单元格，每个集装箱的重量为 3。将所有集装箱装载后，总重量为 12，未超过 maxWeight。

示例 2：

输入： n = 3, w = 5, maxWeight = 20

输出： 4

解释：

甲板有 9 个单元格，每个集装箱的重量为 5。可以装载的最大集装箱数量为 4，此时总重量不超过 maxWeight。

 

提示：

  • 1 <= n <= 1000
  • 1 <= w <= 1000
  • 1 <= maxWeight <= 109

解法

方法一：数学

思考

甲板有 \(n^2\) 个格，每格最多一箱，每箱重 \(w\)，总重不超过 \(\textit{maxWeight}\)。

箱数还受格子数限制，故为 \(\min(n^2,\lfloor \textit{maxWeight}/w\rfloor)\)，也就是 \(\lfloor\min(n^2 w,\textit{maxWeight})/w\rfloor\)。

常数时间取最小再整除即可，无需模拟装载。

我们先计算出船上可以装载的最大重量，即 \(n \times n \times w\)，然后取其与 \(\text{maxWeight}\) 的最小值，再除以 \(w\) 即可。

时间复杂度 \(O(1)\)，空间复杂度 \(O(1)\)。

1
2
3
class Solution:
    def maxContainers(self, n: int, w: int, maxWeight: int) -> int:
        return min(n * n * w, maxWeight) // w

1
2
3
4
5
class Solution {
    public int maxContainers(int n, int w, int maxWeight) {
        return Math.min(n * n * w, maxWeight) / w;
    }
}

1
2
3
4
5
6
class Solution {
public:
    int maxContainers(int n, int w, int maxWeight) {
        return min(n * n * w, maxWeight) / w;
    }
};

1
2
3
func maxContainers(n int, w int, maxWeight int) int {
    return min(n*n*w, maxWeight) / w
}

1
2
3
function maxContainers(n: number, w: number, maxWeight: number): number {
    return (Math.min(n * n * w, maxWeight) / w) | 0;
}

评论