1058_最小化舍入误差以满足目标

类型：堆

1. 最小化舍入误差以满足目标 💛 ⭐
https://leetcode-cn.com/problems/minimize-rounding-error-to-meet-target/

❓ 给定一系列价格数组 prices 和一个目标 target。对于 prices[i] 我们可以对其进行向下取整（floor）或向上取整（ceil），我们对 prices 数组中的元素进行取整操作（不同元素可以采用不同取整方案），使得最终数组和等于 target。我们定义舍入误差为 $Σ |Roundi(pi) - (pi)|$（ i 从 1 到 n ）。求最小的舍入误差。若无论如何舍入，都不能等于 target，则返回 -1。

输入：prices = [“0.700”,“2.800”,“4.900”], target = 8 输出：“1.000” 解释：使用 Floor，Ceil 和 Ceil 操作得到 (0.7 - 0) + (3 - 2.8) + (5 - 4.9) = 0.7 + 0.2 + 0.1 = 1.0 。

💡 堆

对所有元素取 floor 可以得到最小和 minSum 对所有元素取 ceil 可以得到最大和 maxSum 如果 target 不在此区间，则返回 “-1”

对于大部分元素而言，取 ceil 和取 floor 的差值为 1，但是，本身是整数的元素除外。 这是此题的一个非常容易忽略的陷阱。计算 target 与 minSum 的差值，target - minSum = ceilNum，这说明我们需要在 minSum 的基础上，将 ceilNum 个元素改为 ceil 处理（注意，这几个元素不能是整数），以保证和等于 target。要使得绝对差之和最小，我们需要尽量选取 ceil(price) - price 小的元素。通过维护一个大小为 ceilNum 的大顶堆可以实现。
```
class Solution:
    def minimizeError(self, prices: List[str], target: int) -> str:
        if not prices and target != 0: return "-1"

        minSum = sum(math.floor(float(price)) for price in prices)
        maxSum = sum(math.ceil(float(price)) for price in prices)
        if minSum > target or maxSum < target:
            return "-1"

        ceilNum = target - minSum
        heap = []
        for i, price in enumerate(prices):
            price = float(price)
            diff = math.ceil(price) - price
            if diff == 0:
                continue
            if len(heap) < ceilNum or (len(heap) > 0 and diff < -heap[0][0]):
                heapq.heappush(heap, [-diff, i])
            if len(heap) > ceilNum:
                heapq.heappop(heap)

        for i in range(len(heap)):
            heap[i][0] *= -1
        ans = sum(float(price) for price in prices) - minSum
        for (diff, i) in heap:
            price = float(prices[i])
            ans = ans - (price - math.floor(price)) + diff
        return str(format(ans, '.3f'))
```