Задача: 1058. Minimize Rounding Error to Meet Target
Сложность: medium

Учитывая массив цен [p1,p2...,pn] и цель, округлите каждую цену pi до Roundi(pi) так, чтобы округленный массив [Round1(p1),Round2(p2)...,Roundn(pn)] в сумме достиг заданной цели. Каждая операция Roundi(pi) может быть либо Floor(pi), либо Ceil(pi). Верните строку "-1", если округленный массив невозможно привести к целевому значению. В противном случае возвращается наименьшая ошибка округления, которая определяется как Σ |Roundi(pi) - (pi)| для i от 1 до n, в виде строки с тремя местами после десятичной дроби.

Пример:

Input: prices = ["0.700","2.800","4.900"], target = 8
Output: "1.000"

👨‍💻 Алгоритм:

1⃣Округли каждую цену вниз и вычисли текущую сумму округленных цен.
Найди разницу между целевой суммой и текущей суммой.

2⃣Определи количество округлений вверх, необходимых для достижения целевой суммы.
Если разница отрицательная или больше количества элементов в массиве, верни "-1".

3⃣Вычисли ошибки округления для всех элементов и отсортируй их по возрастанию.
Выбери необходимые округления вверх и вычисли общую ошибку округления.

😎 Решение:

function minimizeRoundingError(prices, target) {
    let floors = prices.map(p => Math.floor(parseFloat(p)));
    let totalFloor = floors.reduce((a, b) => a + b, 0);
    
    let difference = target - totalFloor;
    if (difference < 0 || difference > prices.length) {
        return "-1";
    }
    
    let roundingErrors = prices.map((p, i) => [Math.ceil(parseFloat(p)) - floors[i], parseFloat(p) - floors[i]]);
    roundingErrors.sort((a, b) => a[1] - b[1]);
    
    let roundingErrorSum = floors.reduce((sum, floor, i) => sum + (floor - parseFloat(prices[i])), 0);
    
    for (let i = 0; i < difference; i++) {
        roundingErrorSum += roundingErrors[i][1];
    }
    
    return roundingErrorSum.toFixed(3);
}

Ставь 👍 и забирай 📚 Базу знаний