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
1
to n
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
prices[i]
represents a real number in the range [0.0, 1000.0]
and has exactly 3 decimal places.0 <= target <= 106
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);
}