|
| 1 | +#!/usr/bin/python3 |
| 2 | +""" |
| 3 | +Given an array of prices [p1,p2...,pn] and a target, round each price pi to |
| 4 | +Roundi(pi) so that the rounded array [Round1(p1),Round2(p2)...,Roundn(pn)] sums |
| 5 | +to the given target. Each operation Roundi(pi) could be either Floor(pi) or |
| 6 | +Ceil(pi). |
| 7 | +
|
| 8 | +Return the string "-1" if the rounded array is impossible to sum to target. |
| 9 | +Otherwise, return the smallest rounding error, which is defined as |
| 10 | +Σ |Roundi(pi) - (pi)| for i from 1 to n, as a string with three places after the |
| 11 | +decimal. |
| 12 | +
|
| 13 | +
|
| 14 | +
|
| 15 | +Example 1: |
| 16 | +
|
| 17 | +Input: prices = ["0.700","2.800","4.900"], target = 8 |
| 18 | +Output: "1.000" |
| 19 | +Explanation: |
| 20 | +Use Floor, Ceil and Ceil operations to get (0.7 - 0) + (3 - 2.8) + (5 - 4.9) = |
| 21 | +0.7 + 0.2 + 0.1 = 1.0 . |
| 22 | +Example 2: |
| 23 | +
|
| 24 | +Input: prices = ["1.500","2.500","3.500"], target = 10 |
| 25 | +Output: "-1" |
| 26 | +Explanation: |
| 27 | +It is impossible to meet the target. |
| 28 | +
|
| 29 | +
|
| 30 | +Note: |
| 31 | +
|
| 32 | +1 <= prices.length <= 500. |
| 33 | +Each string of prices prices[i] represents a real number which is between 0 and |
| 34 | +1000 and has exactly 3 decimal places. |
| 35 | +target is between 0 and 1000000. |
| 36 | +""" |
| 37 | +fromtypingimportList |
| 38 | +importmath |
| 39 | + |
| 40 | + |
| 41 | +classSolution: |
| 42 | +defminimizeError(self,prices:List[str],target:int)->str: |
| 43 | +""" |
| 44 | + to determine possible, floor all or ceil all |
| 45 | +
|
| 46 | + floor all, sort by floor error inverse, make the adjustment |
| 47 | + """ |
| 48 | +A=list(map(float,prices)) |
| 49 | +f_sum=sum(map(math.floor,A)) |
| 50 | +c_sum=sum(map(math.ceil,A)) |
| 51 | +ifnotf_sum<=target<=c_sum: |
| 52 | +return"-1" |
| 53 | + |
| 54 | +errors= [ |
| 55 | +e-math.floor(e) |
| 56 | +foreinA |
| 57 | + ] |
| 58 | +errors.sort(reverse=True) |
| 59 | +ret=0 |
| 60 | +remain=target-f_sum |
| 61 | +forerrinerrors: |
| 62 | +ifremain>0: |
| 63 | +ret+=1-err |
| 64 | +remain-=1 |
| 65 | +else: |
| 66 | +ret+=err |
| 67 | + |
| 68 | +returnf'{ret:.{3}f}' |