最小化舍入误差以满足目标~leetcode春季高校编程大赛~python

野性酷女 2022-02-19 14:43 131阅读 0赞

题目描述：

难度：Medium

> 给定一系列价格 `[p1,p2...,pn]` 和一个目标 `target`，将每个价格 `pi` 舍入为 `Roundi(pi)` 以使得舍入数组 `[Round1(p1),Round2(p2)...,Roundn(pn)]` 之和达到给定的目标值 `target`。每次舍入操作 `Roundi(pi)` 可以是向下舍 `Floor(pi)` 也可以是向上入 `Ceil(pi)`。
> 
> 如果舍入数组之和无论如何都无法达到目标值 `target`，就返回 `-1`。否则，以保留到小数点后三位的字符串格式返回最小的舍入误差，其定义为 Σ |Roundi(pi) - (pi)|（ i 从 1 到 n ）。

>     输入：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 。

>     输入：prices = ["1.500","2.500","3.500"], target = 10
>     输出："-1"
>     解释：
>     达到目标是不可能的。

> 1.  `1 <= prices.length <= 500`
> 2.  表示价格的每个字符串 `prices[i]` 都代表一个介于 0 和 1000 之间的实数，并且正好有 3 个小数位。
> 3.  `target` 介于 0 和 1000000 之间。

\----------------------------------------------------------答题区----------------------------------------------------------

思路：先把prices中的数向下取整，得出一个最小价格，再向上取整得出一个最大价格，先判断目标价格是否位于这两个价格之间，如果在，接着我们可以先假设都以向下取整的形式，确定出与目标价格相差几元，这个数字就是本应该向上取整的，其余则就是向下取整的。题目规定要取最小误差，那自然向上取整的就选小数点部分最大的，把误差加在一起即可。

需要注意的一点是由于涉及浮点数的运算，会有精度丢失，还好题目规定是保留三位小数，造成的影响不大，不用特殊处理。

class Solution:
        def minimizeError(self, prices: List[str], target: int) -> str:
            import math      
            prices=[float(i) for i in prices]
            lst=[]
            max_price,min_price,res=0,0,0,     
    
            for i in prices:
                lst.append(i-math.floor(i)) #取出每个数的小数部分
                max_price+=math.ceil(i)
                min_price+=math.floor(i)
    
            if(target>max_price or target<min_price):
                return "-1"    
            
            lst.sort(reverse=False)  #从低到高
    
            for i in range(target-min_price): #每次取最后一个即是最大的，然后弹出
                res+=(1-lst[-1])
                lst.pop()
            
            res+=sum(lst) #将向下取整的和与向上取整的和加在一起
    
            return '%.3f' % round(res,3)