难度: Medium
Submission
运行时间: 31 ms
内存: 16.1 MB
class Solution:
def minimizeError(self, prices: List[str], target: int) -> str:
ans = []
cur = 0
for price in prices:
price = float(price)
cur += int(price)
add = price - int(price)
if add > 0:
ans.append(add)
if target < cur or target > cur + len(ans):
return "-1"
gap = target - cur
ans.sort(reverse=True)
rest = gap - sum(ans[:gap]) + sum(ans[gap:])
return "%.3f" % rest
Explain
这个题解首先将每个价格字符串转换为浮点数，并分解为整数部分和小数部分。整数部分直接累加以计算所有价格的整数总和。而小数部分（如果大于0）被收集到一个列表中，这些是可以通过支付额外的费用（即向上舍入）来调整的部分。接着，题解检查目标值是否可达。如果目标值小于当前整数总和或大于整数总和加上可以调整的价格数量（也即小数部分列表长度），则返回'-1'表示无法达成目标。否则，将小数部分列表按从大到小排序，计算通过向上舍入最大的几个小数部分以最小化总舍入误差，直到达到目标值。最终，输出总误差，格式化为三位小数。
时间复杂度: O(n log n)
空间复杂度: O(n)
class Solution:
def minimizeError(self, prices: List[str], target: int) -> str:
ans = [] # 用于存储所有价格的小数部分
cur = 0 # 用于累计所有价格的整数部分总和
for price in prices:
price = float(price)
cur += int(price)
add = price - int(price)
if add > 0:
ans.append(add) # 仅添加非零的小数部分
if target < cur or target > cur + len(ans):
return "-1" # 目标不可达
gap = target - cur
ans.sort(reverse=True) # 将小数部分从大到小排序
rest = gap - sum(ans[:gap]) + sum(ans[gap:]) # 计算最终的舍入误差
return "%.3f" % rest # 格式化输出误差，保留三位小数
Explore
这种方法基于贪心算法的逻辑。贪心算法选择每一步的局部最优解，希望通过这种方式达到全局最优解。在本题中，通过选择最大的小数部分先进行向上舍入，可以尽量减少达到目标整数时的总舍入误差，因为较大的小数部分向上舍入带来的误差增加相对较小。这种方法试图通过最大限度地利用每次舍入的'价值'，来最小化总误差。
这种检查是为了确认目标值是否在可能的范围内。整数总和代表了没有进行任何舍入操作时所有价格的总和。整数总和加上可调整的价格数量（即有小数部分的价格数）表示所有价格都进行向上舍入后的最大可能总和。如果目标值小于不进行舍入的最小值或者大于最大可能的舍入值，那么这个目标值就是不可达的，因为无论如何舍入，都无法精确达到目标值。
虽然这种方法在很多情况下能够达到较好的效果，但并不是在所有情况下都是最优的。例如，如果小数部分的分布与目标舍入次数之间存在特定的模式，简单的贪心策略可能不会产生最小的总舍入误差。此外，这种方法假设每次向上舍入大的小数部分总是最佳选择，但在某些特殊组合下，可能会有其他舍入组合提供更小的误差。
这种计算方式是为了更精确和简化计算过程。通过先对小数部分进行排序和分类，可以更容易地管理哪些小数部分被向上舍入，哪些被保留。这样做可以在确定了需要向上舍入的小数个数后，直接计算出总的误差值。如果在遍历每个价格时直接计算总误差，会因为还未决定哪些小数部分需要向上舍入而复杂化问题，增加错误和计算复杂度。