Leetcode 2819. 购买巧克力后的最小相对损失

1.题目基本信息

1.1.题目描述

现给定一个整数数组 prices，表示巧克力的价格；以及一个二维整数数组 queries，其中 queries[i] = [ki, mi]。

Alice 和 Bob 去买巧克力，Alice 提出了一种付款方式，而 Bob 同意了。

对于每个 queries[i] ，它的条件如下：

• 如果一块巧克力的价格 小于等于 ki，那么 Bob 为它付款。

• 否则，Bob 为其中 ki 部分付款，而 Alice 为 剩余 部分付款。

Bob 想要选择 恰好 mi 块巧克力，使得他的 相对损失最小 。更具体地说，如果总共 Alice 付款了 ai，Bob 付款了 bi，那么 Bob 希望最小化 bi - ai。

返回一个整数数组 ans，其中 ans[i] 是 Bob 在 queries[i] 中可能的 最小相对损失 。

1.2.题目地址

https://leetcode.cn/problems/minimum-relative-loss-after-buying-chocolates/description/

2.解题方法

2.1.解题思路

滑动窗口+二分查找

2.2.解题步骤

第一步，记n=len(prices)，将prices升序排列

第二步，枚举每一个queries[i]=[k,m]

• 2.1.构建losses数组，如果prices[i]<=k，losses[i]=prices[i]；如果prices[i]>k，losses[i]=k-(prices[i]-k)=2*k-prices[i]；并求losses数组的前缀和数组lossPreSums，则可以在O(1)时间内查询到子数组的和

• 2.2.证明：由prices递增可知，losses一定是先非严格递增后非严格递减，那么要让总损失最小，只能取larr1=losses[0,1,...,x]和larr2=losses[n-m+x+1,...,n-1]，此时的损失f(x)=sum(larr1)+sum(larr2)=sum(prices[0,...,x])+sum([2k-prices[i] for i in [x+n-m+1,...,n-1]])，则f(x+1)-f(x)=prices[x]+prices[x+n-m+1]-2k，可知f(x)是先递减后递增的；那么对于中间长度为n-m的滑动窗口的和val=sum(losses[x+1,...,x+n-m])就是先递增后递减的，只要找到val的最大值，就找到了最小损失值

3.解题代码

python代码

from bisect import bisect_leftclass Solution:def minimumRelativeLosses(self, prices: List[int], queries: List[List[int]]) -> List[int]:# 思路1：滑动窗口+二分查找# 第一步，记n=len(prices)，将prices升序排列；并前缀和数组，preSums[i]为前i项的前缀和n = len(prices)preSums = [0]prices.sort()for i in range(n):preSums.append(preSums[-1] + prices[i])# print("preSums", preSums)# 第二步，枚举每一个queries[i]=[k,m]result = []for k, m in queries:# 2.1.证明：由prices递增可知，losses一定是先非严格递增后非严格递减，那么要让总损失最小，只能取larr1=losses[0,1,...,x]和larr2=losses[n-m+x+1,...,n-1]，此时的损失f(x)=sum(larr1)+sum(larr2)=sum(prices[0,...,x])+sum([2k-prices[i] for i in [x+n-m+1,...,n-1]])，则f(x+1)-f(x)=prices[x]+prices[x+n-m+1]-2k，可知f(x)是先递减后递增的；那么对于中间长度为n-m的滑动窗口的和val=sum(losses[x+1,...,x+n-m])就是先递增后递减的，只要找到val的最大值，就找到了最小损失值# 2.2.找到第一个price大于等于k的索引位置，记为p1p1 = bisect_left(prices, k)# print("p1", p1)# 2.3.从[0,...,p1]中找到第一个index，记index2=index+(n-m)，使prices[index]>=2*k-prices[index2]。红蓝染色不变量：prices[left-1]<2*k-prices[index2]恒成立，最终的left即为要找的indexleft, right = 0, p1while left < right:mid = (right - left) // 2 + leftindex2 = mid + n - mif index2 < n and prices[mid] < 2 * k - prices[index2]:left = mid + 1else:right = midindex = left# print("left, right", left, right)# 2.4.根据index求最小损失，minLoss=sum(prices[0,...,index-1])+sum([2*k-prices[j] for j in [index+n-m,...,n-1]])val = preSums[index] + 2 * k * (m - index) - (preSums[n] - preSums[index + n - m])result.append(val)return result

4.执行结果