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.

Example 3:

Input: prices = ["1.500","2.500","3.500"], target = 9
Output: "1.500"

 

Constraints:

  • 1 <= prices.length <= 500
  • Each string prices[i] represents a real number in the range [0.0, 1000.0] and has exactly 3 decimal places.
  • 0 <= target <= 106

1058. Minimize Rounding Error to Meet Target
struct Solution;

impl Solution {
    fn minimize_error(prices: Vec<String>, target: i32) -> String {
        let prices: Vec<f64> = prices
            .into_iter()
            .map(|x| x.parse::<f64>().unwrap())
            .collect();
        let floor: i32 = prices.iter().map(|x| x.floor() as i32).sum();
        let ceil: i32 = prices.iter().map(|x| x.ceil() as i32).sum();
        let n = prices.len();
        if target < floor || target > ceil {
            return "-1".to_string();
        }
        let m = (target - floor) as usize;
        let mut diff = vec![];
        for i in 0..n {
            if prices[i].floor() as i32 != prices[i].ceil() as i32 {
                diff.push(prices[i].ceil() as f64 - prices[i]);
            }
        }
        let mut sum = 0.0;
        diff.sort_by(|a, b| a.partial_cmp(b).unwrap());
        for i in 0..diff.len() {
            if i < m {
                sum += diff[i];
            } else {
                sum += 1.0 - diff[i];
            }
        }

        format!("{:.3}", sum)
    }
}

#[test]
fn test() {
    let prices = vec_string!["0.700", "2.800", "4.900"];
    let target = 8;
    let res = "1.000".to_string();
    assert_eq!(Solution::minimize_error(prices, target), res);
    let prices = vec_string!["1.500", "2.500", "3.500"];
    let target = 10;
    let res = "-1".to_string();
    assert_eq!(Solution::minimize_error(prices, target), res);
}