LeetCode 1058. 最小化舍入误差以满足目标

2022-03-03 HGNULB 约 7 分钟

文章信息 6 个分类 5 个标签

分类

题目描述

✅ 1058. 最小化舍入误差以满足目标

题意分析

给一组以字符串形式表示的价格（每个都带三位小数），要求把每个价格要么向下取整、要么向上取整，使得取整后的总和恰好等于 target；在所有可行方案中，让「误差」最小并按三位小数返回。误差定义为每个价格取整前后差值的绝对值之和，即 Σ |round(p_i) - p_i|。若无法凑出 target，返回 "-1"。

有三点必须先看清。第一，每个价格只有两个选择，没有第三种可能，所以方案空间是 $2^n$ 的，但每个选择的代价是独立可加的——这是能贪心的前提。第二，总和被硬性钉死在 target，这把 n 个独立选择耦合成了「必须恰好选 diff 个向上取整」的名额约束。第三，对一个整数价格（小数部分为 0），向上和向下取整得到同一个数，它对总和的贡献是固定的，对误差的贡献也恒为 0，根本无法用来调节总和——这是本题最容易漏掉的性质。

由此可以把问题标准化：设第 i 个价格的小数部分是 f_i。向下取整的代价是 f_i，向上取整的代价是 1 - f_i（当 f_i > 0 时）。若全部向下取整，总和是 sumFloor；每把一个小数部分非零的价格改成向上取整，总和恰好增加 1。所以需要向上取整的个数就是 diff = target - sumFloor。

可行性条件随之明确：diff 必须落在 [0, 非整数价格的个数] 之间。diff < 0 说明连全部下取整都超过了 target；diff 超过非整数个数说明就算全部上取整也够不到 target。

约束是 1 ≤ prices.length ≤ 500，价格在 [0, 1000]，0 ≤ target ≤ 10^6。规模很小，$O(n \log n)$ 排序毫无压力；sumFloor 与 target 都在 int 范围内。

边界：所有价格都是整数时，非整数个数为 0，只有 diff == 0 才可行，误差为 0；diff == 0 时全部下取整；diff 等于非整数个数时全部上取整。

解法：贪心选择上取整

核心思路

每个价格固定有三位小数，可以把误差统一放大 1000 倍，用整数精确计算。设价格的整数部分为 whole，小数部分对应的整数为 frac ∈ [0, 999]：向下取整的误差是 frac，非整数价格向上取整的误差是 1000 - frac。

先让所有价格向下取整。此时总和为 sumFloor，总误差为 Σ frac。每把一个非整数价格改为向上取整，总和恰好增加 1，所以必须选择

up = target - sumFloor

个非整数价格向上取整。若 up < 0，说明全部向下仍超过目标；若 up > nonIntegerCount，说明全部可上取整的价格都上取整仍达不到目标。这两种情况都无解。

将小数部分为 frac 的价格从向下改为向上，误差变化量为

(1000 - frac) - frac = 1000 - 2 × frac。

因为变化量随 frac 增大而减小，应选择小数部分最大的 up 个价格向上取整。

贪心不变量：小数部分排序后，已选的向上取整集合始终是当前最大的若干个 frac。若某个方案选择了较小的 a，却没选择较大的 b，交换两者不改变向上取整的数量和最终总和，误差变化为 2(a - b) ≤ 0，方案不会变差。不断交换后必能得到“选择最大的 up 个”的最优方案。

正确性：可行性检查保证恰好存在 up 个非整数价格可改为向上取整，因此最终整数和一定等于 target；交换论证又保证在所有满足该总和的方案中，选择最大的 up 个小数部分误差最小。千分位整数计算与题目的三位小数完全等价，所以格式化后的结果就是最小总舍入误差。

使用千分位整数而不是浮点数，还避免了二进制浮点表示和格式化舍入带来的末位风险。

解题步骤

解析每个价格的整数部分和三位小数部分，累加 sumFloor 与初始误差 errorMillis；只把非零小数部分放入候选数组。

计算 up = target - sumFloor，检查它是否位于 [0, nonIntegerCount]，否则返回 "-1"。

将候选小数部分升序排序，选择末尾最大的 up 个；对每个被选项，把误差加上 1000 - 2 × frac。

将千分位误差拆成整数部分和三位小数，按 x.xxx 返回。

对 prices = ["0.700", "2.800", "4.900"]、target = 8，全部向下时 sumFloor = 6、误差为 2400，需要两个价格向上。选择最大的 900 和 800 后，误差变为 2400 - 800 - 600 = 1000，返回 "1.000"。

整数价格不能占用向上名额。例如 prices = ["1.000", "2.500"]、target = 5 时，全部向下为 3，虽然有两个价格，但只有 2.500 能让总和增加 1，最大总和是 4，因此必须返回 "-1"。

代码实现

class Solution {
    public String minimizeError(String[] prices, int target) {
        int[] fractions = new int[prices.length];
        int count = 0;
        int sumFloor = 0;
        int errorMillis = 0;

        for (String price : prices) {
            int dot = price.indexOf('.');
            int whole = Integer.parseInt(price.substring(0, dot));
            int fraction = Integer.parseInt(price.substring(dot + 1));
            sumFloor += whole;
            errorMillis += fraction;
            if (fraction != 0) {
                fractions[count++] = fraction;
            }
        }

        int up = target - sumFloor;
        if (up < 0 || up > count) {
            return "-1";
        }

        java.util.Arrays.sort(fractions, 0, count);
        for (int i = count - up; i < count; i++) {
            errorMillis += 1000 - 2 * fractions[i];
        }
        return String.format(java.util.Locale.ROOT, "%d.%03d",
                errorMillis / 1000, errorMillis % 1000);
    }
}

import (
	"fmt"
	"sort"
)

func minimizeError(prices []string, target int) string {
	fractions := make([]int, 0, len(prices))
	sumFloor, errorMillis := 0, 0

	for _, price := range prices {
		whole, fraction := 0, 0
		fmt.Sscanf(price, "%d.%d", &whole, &fraction)
		sumFloor += whole
		errorMillis += fraction
		if fraction != 0 {
			fractions = append(fractions, fraction)
		}
	}

	up := target - sumFloor
	if up < 0 || up > len(fractions) {
		return "-1"
	}

	sort.Ints(fractions)
	for i := len(fractions) - up; i < len(fractions); i++ {
		errorMillis += 1000 - 2*fractions[i]
	}
	return fmt.Sprintf("%d.%03d", errorMillis/1000, errorMillis%1000)
}

复杂度分析

时间复杂度：$O(n \log n)$，排序非整数价格的小数部分占主导，其余遍历均为 $O(n)$。

空间复杂度：$O(n)$，候选数组最多保存 n 个小数部分；误差计算本身只使用常数空间。

关键点总结

先以“全部向下”为基准，目标总和直接决定必须向上的数量 up。

小数部分为 0 的价格没有两种不同选择，不能计入可向上取整的候选数。

向上取整的误差增量是 1000 - 2 × frac，因此选择最大的 frac；交换论证保证该贪心全局最优。

固定三位小数适合转成千分位整数，计算和输出都能保持精确。

易错点总结

把整数价格也当作可向上取整：["1.000", "2.500"]、target = 5 会被误判为可行；整数的 ceil 与 floor 相同，不能让总和增加。

贪心方向反了：样例中若选择 700 和 800 向上，误差为 1.400；选择最大的 900 和 800 才得到最优的 1.000。

漏掉一侧可行性判断：["2.900"]、target = 1 对应 up = -1；["1.100"]、target = 3 对应 up = 2 > 1，两者都应返回 "-1"。

直接用四舍五入决定方向：每个价格的局部最优可能使总和不等于 target；本题先满足精确的向上名额，再在合法方案中最小化误差。

用浮点数比较小数部分或累计误差：在临界值附近可能因表示误差导致排序或末位格式化不稳定；输入固定三位小数，整数千分位更直接可靠。

输出未补足三位：误差 1 必须返回 "1.000"，无解则必须返回 "-1"，不能返回 "1" 或 "-1.000"。

相似题目

题目	难度	考察点
1029. 两地调度	中等	同为「基准 + 增量差值排序取前 k」，但名额固定为一半且不存在「无解」分支
1005. K 次取反后最大化的数组和	简单	操作次数固定，但同一元素可重复操作，多出奇偶性讨论
455. 分发饼干	简单	两边各自排序后双指针匹配，贪心对象是配对而非二选一
881. 救生艇	中等	排序后头尾双指针，每步要同时考虑最轻与最重两端
502. IPO	困难	同样是「恰好选 k 个」，但候选随资本增长动态解锁，需要排序配合大顶堆
630. 课程表 III	困难	反悔式贪心：已选中的元素还能被更优的替换掉，普通排序取前缀不再成立
976. 三角形的最大周长	简单	排序后取第一组合法三元组，贪心依据是可行性约束而非收益大小