Formatted question description: https://leetcode.ca/all/1058.html

# 1058. Minimize Rounding Error to Meet Target

## Level

Medium

## Description

Given an array of prices `[p_1,p_2...,p_n]`

and a `target`

, round each price `p_i`

to `Round_i(p_i)`

so that the rounded array `[Round_1(p_1),Round_2(p_2)...,Round_n(p_n)]`

sums to the given `target`

. Each operation `Round_i(p_i)`

could be either `Floor(p_i)`

or `Ceil(p_i)`

.

Return the string `"-1"` if the rounded array is impossible to sum to `target` . Otherwise, return the smallest rounding error, which is defined as Σ |
Round_{i}(p_{i}) - (p_{i}) |
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 <= prices.length <= 500`

.- Each string of prices
`prices[i]`

represents a real number which is between 0 and 1000 and has exactly 3 decimal places. `target`

is between 0 and 1000000.

## Solution

Since each `price`

in `prices`

has exactly 3 decimal places, multiply each `price`

and `target`

by 1000 to make all the numbers become integers. Do floor operation on all prices to obtain the smallest possible sum, and do ceiling operation on all prices to obtain the greatest possible sum. If `target`

is not in the range, return `"-1"`

.

Calculate the difference between `target`

and the smallest possible sum, and obtain the number of prices that need to be changed to ceiling operation. The prices with greater remainders when divided by 1000 (or greater fraction part before multiplied by 1000) should be considered first so that the rounding error can be reduced the most. Use a priority queue to store all the prices, where the prices with greater remainders when divided by 1000 are polled first. Each time poll a price and change the floor operation to ceiling operation, and update the rounding error. Repeat the process until `target`

is met. Finally, return the rounding error.

```
class Solution {
public String minimizeError(String[] prices, int target) {
int length = prices.length;
int[] priceArray = new int[length];
int[] minArray = new int[length];
int[] maxArray = new int[length];
int minSum = 0, maxSum = 0, errorSum = 0;
for (int i = 0; i < length; i++) {
String priceStr = prices[i];
int pointIndex = priceStr.indexOf('.');
String iPart = priceStr.substring(0, pointIndex);
String fPart = priceStr.substring(pointIndex + 1);
int price = Integer.parseInt(iPart) * 1000 + Integer.parseInt(fPart);
priceArray[i] = price;
if (price % 1000 == 0) {
minArray[i] = price;
maxArray[i] = price;
} else {
minArray[i] = price / 1000 * 1000;
maxArray[i] = minArray[i] + 1000;
}
minSum += minArray[i];
maxSum += maxArray[i];
errorSum += price - minArray[i];
}
int targetThousand = target * 1000;
if (targetThousand > maxSum || targetThousand < minSum)
return "-1";
int difference = targetThousand - minSum;
PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(new Comparator<Integer>() {
public int compare(Integer num1, Integer num2) {
return num2 % 1000 - num1 % 1000;
}
});
for (int i = 0; i < length; i++)
priorityQueue.offer(priceArray[i]);
for (int i = 0; i < difference; i += 1000) {
int price = priorityQueue.poll();
int remainder = price % 1000;
int newRemainder = 1000 - remainder;
errorSum -= (remainder - newRemainder);
}
String minErrorIPart = String.valueOf(errorSum / 1000);
String minErrorFPart = String.format("%03d", errorSum % 1000);
String minError = minErrorIPart + "." + minErrorFPart;
return minError;
}
}
```