77 lines
3.0 KiB
Python
77 lines
3.0 KiB
Python
"""
|
||
输入一个数组 ht，其中的每个元素代表一个垂直隔板的高度。数组中的任意两个隔板，以及它们之间的空间可以组成一个容器。
|
||
容器的容量等于高度和宽度的乘积（面积），其中高度由较短的隔板决定，宽度是两个隔板的数组索引之差。
|
||
请在数组中选择两个隔板，使得组成的容器的容量最大，返回最大容量。
|
||
|
||
容器由任意两个隔板围成，因此本题的状态为两个隔板的索引，记为 [i,j]。
|
||
|
||
根据题意，容量等于高度乘以宽度，其中高度由短板决定，宽度是两隔板的数组索引之差。设容量为 cap[i,j]，则可得计算公式：
|
||
cap[i,j] = min(ht[i],ht[j]) * (j - i)
|
||
|
||
贪心策略确定:
|
||
|
||
- 现选取一个状态 [i, j]，其满足索引 i<j 且高度 ht[i]<ht[j]。
|
||
- 若此时将长板 j 向短板 i 靠近，则容量一定变小。因为i仍然是短板。
|
||
- 向内移动i，i的高度增大后，容量才可能变大。
|
||
- 由此便可推出本题的贪心策略：初始化两指针分列容器两端，每轮向内收缩短板对应的指针，直至两指针相遇。
|
||
"""
|
||
import math
|
||
|
||
|
||
def max_capacity(ht: list[int]) -> int:
|
||
i, j = 0, len(ht) - 1
|
||
res = 0
|
||
while i < j:
|
||
cap = min(ht[i], ht[j]) * (j - i)
|
||
res = max(res, cap)
|
||
if ht[i] < ht[j]:
|
||
i += 1
|
||
else:
|
||
j -= 1
|
||
return res
|
||
|
||
|
||
"""
|
||
最大切分乘积问题：
|
||
|
||
给定一个正整数 n，将其切分为至少两个正整数的和，求切分后所有整数的乘积最大是多少?
|
||
|
||
假设我们将 n 切分为 m 个整数因子，其中第 i 个因子记为 ni
|
||
|
||
贪心策略确定：
|
||
|
||
根据经验，两个整数的乘积往往比它们的加和更大。假设从 n 中分出一个因子 2，
|
||
则它们的乘积为 2(n-2)。我们将该乘积与 n 作比较：
|
||
2*(n-2)>=n --> n>=4
|
||
|
||
也就是当 n>=4 时，切分出一个 2 后乘积会变大，这说明大于等于 4 的整数都应该被切分。
|
||
|
||
贪心策略一：如果切分方案中包含 >=4 的因子，那么它就应该被继续切分。最终的切分方案只应出现 1、2、3这三个因子。
|
||
在 1、2、3 这三个因子中，显然 1 是最差的，因为 1*(n-1)<n恒成立。
|
||
|
||
贪心策略二：在切分方案中，最多只应存在两个 2。因为三个 2，总是可以替换为两个 3，从而获得更大的乘积。
|
||
|
||
代码实现：
|
||
我们无须通过循环来切分整数，而可以利用向下整除运算得到 3 的个数 a，用取模运算得到余数 b，
|
||
此时有：
|
||
n = 3a + b
|
||
|
||
请注意，对于 n<=3 的边界情况，必须拆分出一个 1，乘积为 1(n-1)。
|
||
"""
|
||
|
||
|
||
def max_product_cutting(n: int) -> int:
|
||
if n <= 3:
|
||
return 1 * (n - 1)
|
||
|
||
a, b = n // 3, n % 3
|
||
if b == 1:
|
||
# 当余数为 1 时，将一对 1 * 3 转为 2 * 2
|
||
return int(math.pow(3, a - 1)) * 2 * 2
|
||
if b == 2:
|
||
# 当余数为 2 时不用处理
|
||
return int(math.pow(3, a)) * 2
|
||
|
||
# 余数为 0 时不用处理
|
||
return int(math.pow(3, a))
|