[Leetcode 1058] Minimize Rounding Error to Meet Target

原题说明

Given an array of prices [p1,p2…,pn] and a target, round each price pi to Roundi(pi) so that the rounded array [Round1(p1),Round2(p2)…,Roundn(pn)] sums to the given target. Each operation Roundi(pi) could be either Floor(pi) or Ceil(pi).

Return the string “-1” if the rounded array is impossible to sum to target. Otherwise, return the smallest rounding error, which is defined as Σ |Roundi(pi) - (pi)| for i from 1 to n, as a string with three places after the decimal.

 

Example 1:

Input: prices = [“0.700”,”2.800”,”4.900”], target = 8
Output: “1.000”
Explanation: 
Use Floor, Ceil and Ceil operations to get (0.7 - 0) + (3 - 2.8) + (5 - 4.9) = 0.7 + 0.2 + 0.1 = 1.0 .

Example 2:

Input: prices = [“1.500”,”2.500”,”3.500”], target = 10
Output: “-1”
Explanation: 
It is impossible to meet the target.

 

Note:

1. 1 <= prices.length <= 500.
2. Each string of prices prices[i] represents a real number which is between 0 and 1000 and has exactly 3 decimal places.
3. target is between 0 and 1000000.

解题思路

如果一个数字是一个整数， 那么我们只能取floor，不能取ceil。这相当于一个无法调整的数字，否则就是一个可调整的数字。我们把所有可调整的数字的小数部分放入一个priority queue中，把priority queue的size记为pqsize。

然后我们先判断什么情况下无法得到target：

1. 如果取最小的可能的和，那么所有数字都要取floor。如果这个和仍然比target大，或者比target-pqsize小，那么就说明无论如何也不可能得到target。这样我们就返回 “-1”
2. 若满足上述条件，我们一定可以取到满足题目条件的和。我们需要知道调整多少个数字，即把floor操作变成ceil操作。需要调整的数字个数等于target-pqsize。
3. 为了的达到最小的rounding error，对于每个调整的操作，我们希望它们小数尽可能大，这可以由之前的priority queue得到。取那个数字的ceil。最后把所有不需要调整的小数也加上，就是最小的rounding error了。

注意最后返回字符串是，需要做些特殊处理，只保留最后3位小数即可。

示例代码 (cpp)

class Solution {
public:
    string minimizeError(vector<string>& prices, int target) {
        priority_queue<double> pq;
        int sum = 0;
        for (auto price : prices) {
            sum += floor(stod(price));
            double diffPrice = stod(price) - floor(stod(price));
            if (diffPrice != 0) {
                pq.push(diffPrice);
            }
        }
        if (sum > target || sum < target - pq.size()) {
            return "-1";
        }
        int diff = target - sum;
        double error = 0;
        while (!pq.empty()) {
            double fl = pq.top();
            pq.pop();
            error += diff > 0 ? 1 - fl : fl;
            diff--;
        }        
        string ans = to_string(error);
        return ans.substr(0, ans.find('.') + 4);
    }
};

示例代码 (java)

class Solution {
    public String minimizeError(String[] prices, int target) {
        float res = 0;
        PriorityQueue<Double> diffHeap = new PriorityQueue<>();
        
        for (String s : prices) {
            float f = Float.valueOf(s);
            double low = Math.floor(f);
            double high = Math.ceil(f);
            
            if (low != high)
                diffHeap.offer((high-f)-(f-low));
            
            res += f-low;
            target -= low;
        }
        
        if (target < 0 || target > diffHeap.size())
            return "-1";
        
        while (target-- > 0)
            res += diffHeap.poll();
        
        return String.format("%.3f", res);
    }
}

示例代码 (python)

class Solution:
    def minimizeError(self, prices: List[str], target: int) -> str:
        diff = []
        low, high = 0, 0
        for i, p in enumerate(map(float, prices)):
            f, c = math.floor(p), math.ceil(p)
            low, high = low + f, high + c
            fDiff, cDiff = p - f, c - p
            diff.append((fDiff - cDiff, fDiff, cDiff))
        if not low <= target <= high:
            return "-1"
        ceilN = target - low
        diff = sorted(diff, reverse=True)
        return "{:.3f}".format(sum([d[2] for d in diff[:ceilN]]) + sum([d[1] for d in diff[ceilN:]]))

复杂度分析

时间复杂度: O(NlogN)
空间复杂度: O(N)

归纳总结

我们在Youtube上更新了视频讲解，欢迎关注！