Задача: 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) {
    $floors = array_map(function($p) { return floor(floatval($p)); }, $prices);
    $totalFloor = array_sum($floors);
    
    $difference = $target - $totalFloor;
    if ($difference < 0 || $difference > count($prices)) {
        return "-1";
    }
    
    $roundingErrors = [];
    foreach ($prices as $i => $p) {
        $floatP = floatval($p);
        $roundingErrors[] = [ceil($floatP) - $floors[$i], $floatP - $floors[$i]];
    }
    
    usort($roundingErrors, function($a, $b) {
        return $a[1] <=> $b[1];
    });
    
    $roundingErrorSum = 0;
    foreach ($prices as $i => $p) {
        $roundingErrorSum += ($floors[$i] - floatval($p));
    }
    
    for ($i = 0; $i < $difference; $i++) {
        $roundingErrorSum += $roundingErrors[$i][1];
    }
    
    return number_format($roundingErrorSum, 3, '.', '');
}

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