难度: Hard
Submission
运行时间: 618 ms
内存: 60.6 MB
class Solution:
def minimumRelativeLosses(self, prices: List[int], queries: List[List[int]]) -> List[int]:
n = len(prices)
prices.sort()
psum = [0] * (n + 1)
for i, x in enumerate(prices):
psum[i + 1] = psum[i] + x
res = []
for i, (k, m) in enumerate(queries):
if m == n:
x = bisect_right(prices, k)
res.append(psum[x] + 2 * k * (n - x) - (psum[n] - psum[x]))
continue
need, idx = n - m, m
lo, hi = 0, m - 1
while lo <= hi:
mid = (lo + hi) >> 1
if k - prices[mid] > prices[mid + need] - k:
lo = mid + 1
else:
hi, idx = mid - 1, mid
left = psum[idx]
right = 2 * k * (n - idx - need) - (psum[n] - psum[idx + need])
res.append(left + right)
return res
Explain
此题解采用前缀和与二分搜索的方法来解决问题。首先，对价格数组进行排序，以便于后续操作。接着，计算价格数组的前缀和，这有助于快速计算任意连续子数组的和。对于每个查询，首先检查是否需要所有的巧克力，如果是，则直接计算，否则使用二分搜索确定最优的购买位置以最小化损失。二分搜索寻找使得 'k-prices[mid]' 最接近 'prices[mid + need] - k' 的位置，以确保购买的巧克力价格尽可能靠近 k。最后，结合前缀和数组，计算并返回每个查询的结果。
时间复杂度: O(n log n + q log m)
空间复杂度: O(n + q)
class Solution:
def minimumRelativeLosses(self, prices: List[int], queries: List[List[int]]) -> List[int]:
n = len(prices)
prices.sort()
psum = [0] * (n + 1)
for i, x in enumerate(prices):
psum[i + 1] = psum[i] + x # 前缀和计算
res = []
for i, (k, m) in enumerate(queries):
if m == n:
x = bisect_right(prices, k)
res.append(psum[x] + 2 * k * (n - x) - (psum[n] - psum[x]))
continue
need, idx = n - m, m
lo, hi = 0, m - 1
while lo <= hi:
mid = (lo + hi) >> 1
if k - prices[mid] > prices[mid + need] - k:
lo = mid + 1
else:
hi, idx = mid - 1, mid
left = psum[idx]
right = 2 * k * (n - idx - need) - (psum[n] - psum[idx + need])
res.append(left + right)
return res
Explore
算法选择使用二分搜索而不是其他搜索方法的原因在于，数组已经被排序并且我们需要找到一个满足特定条件的点（使得损失最小化）。二分搜索是针对已排序数组的一种高效搜索方法，其时间复杂度为O(log n)，远优于线性搜索的O(n)。通过二分搜索，我们可以快速定位到最接近给定条件的点，从而有效提高算法的执行效率。
这个条件`k - prices[mid] > prices[mid + need] - k`是为了找到使得购买的巧克力价格尽可能接近k的位置。条件的数学基础是最小化差值的绝对值。当`k - prices[mid]`（即k与当前价格的差）大于`prices[mid + need] - k`（即当前价格与需要的价格的差）时，说明mid位置过小，需要向后搜索，从而增大mid值；反之，则说明mid位置过大，需要向前搜索，从而减小mid值。这样的逻辑可以帮助我们找到最小化差值的最佳位置。
这个表达式的计算是基于最小化损失。其中`psum[x]`代表排序后最便宜的x个巧克力的总价格，`psum[n] - psum[x]`是剩余巧克力的总价格。`2 * k * (n - x)`是如果每个巧克力的价格变为k后，剩余巧克力的总价格。因此，整个表达式`psum[x] + 2 * k * (n - x) - (psum[n] - psum[x])`代表的是在k为目标价格时，通过购买x个巧克力后计算的总损失。通过这种方式，算法尝试找到一个x值，使得总损失最小化。
前缀和数组`psum`在本题中的作用是快速计算任意连续子数组的和，这对于重复进行区间和的计算非常有效。如果使用原始的价格数组直接计算子数组的和，则每次查询的时间复杂度将是O(m)，其中m是子数组的长度。使用前缀和数组后，任意子数组的和可以在O(1)时间内通过`psum[j] - psum[i]`计算得出，显著提高了效率。这在面对多个查询时尤为重要，可以有效减少整体的计算时间。