# 1058. Minimize Rounding Error to Meet Target¶

• Time: $O(\texttt{sort})$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution { public: string minimizeError(vector& prices, int target) { // A[i] := (costCeil - costFloor, costCeil, costFloor) // The lower the costCeil - costFloor is, the cheaper to ceil it. vector> A; int sumFloored = 0; int sumCeiled = 0; for (const string& p : prices) { const double price = stod(p); const int floored = floor(price); const int ceiled = ceil(price); sumFloored += floored; sumCeiled += ceiled; const double costFloor = price - static_cast(floored); const double costCeil = static_cast(ceiled) - price; A.emplace_back(costCeil - costFloor, costCeil, costFloor); } if (sumFloored > target || sumCeiled < target) return "-1"; ranges::sort(A); double sumError = 0.0; const int nCeiled = target - sumFloored; for (int i = 0; i < nCeiled; ++i) sumError += get<1>(A[i]); for (int i = nCeiled; i < A.size(); ++i) sumError += get<2>(A[i]); stringstream ss; ss << std::fixed << std::setprecision(3) << sumError; return ss.str(); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 class Solution { public String minimizeError(String[] prices, int target) { // A[i] := (costCeil - costFloor, costCeil, costFloor) // The lower the costCeil - costFloor is, the cheaper to ceil it. List A = new ArrayList<>(); int sumFloored = 0; int sumCeiled = 0; for (final String p : prices) { final double price = Double.parseDouble(p); final int floored = (int) Math.floor(price); final int ceiled = (int) Math.ceil(price); sumFloored += floored; sumCeiled += ceiled; final double costFloor = price - (double) floored; final double costCeil = (double) ceiled - price; A.add(new double[] {costCeil - costFloor, costCeil, costFloor}); } if (sumFloored > target || sumCeiled < target) return "-1"; Collections.sort(A, new Comparator() { @Override public int compare(double[] a, double[] b) { return Double.compare(a[0], b[0]); } }); double sumError = 0.0; final int nCeiled = target - sumFloored; for (int i = 0; i < nCeiled; ++i) sumError += A.get(i)[1]; for (int i = nCeiled; i < A.size(); ++i) sumError += A.get(i)[2]; return String.format("%.3f", sumError); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution: def minimizeError(self, prices: List[str], target: int) -> str: # A[i] := (costCeil - costFloor, costCeil, costFloor) # The lower the costCeil - costFloor is, the cheaper to ceil it. A = [] sumFloored = 0 sumCeiled = 0 for price in map(float, prices): floored = math.floor(price) ceiled = math.ceil(price) sumFloored += floored sumCeiled += ceiled costFloor = price - floored costCeil = ceiled - price A.append((costCeil - costFloor, costCeil, costFloor)) if not sumFloored <= target <= sumCeiled: return '-1' A.sort() nCeiled = target - sumFloored return '{:.3f}'.format(sum(a[1] for a in A[:nCeiled]) + sum(a[2] for a in A[nCeiled:]))