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

2022-03-03 HGNULB 约 5 分钟

文章信息 7 个分类 · 5 个标签

分类

LeetCode CodeTop 中等 未解决 会员题 1-2 字节

标签

数组 字符串 数学 排序 贪心

题目描述

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

题意分析

每个非负价格都以固定三位小数字符串给出，可以独立向下取整或向上取整。要求所有取整结果之和恰好等于整数 target，并使每项取整值与原价格之差的绝对值总和最小。

能满足目标时，返回保留三位小数的最小误差；无法满足时返回 "-1"。整数价格的上下取整结果相同，不能通过把它选择为“向上”来多增加一。

解法：贪心选择上取整

核心思路

[!blue]

先把全部价格都向下取整，得到最低总和 sumFloor。每个非整数价格从向下改成向上，总和恰好增加 1；因此为了达到目标，必须选中恰好 up = target - sumFloor 个非整数价格改为向上。

若 up < 0，最低总和已经超过目标；若 up 超过非整数价格数量，即使全部向上也不够。否则任选这么多个候选都能满足总和，所以先用这个范围检查确定可行性，再优化哪些候选最划算。

为避免浮点误差，把小数部分按千分之一为单位表示成整数 fraction。全部向下时，这一项的误差就是 fraction；改成向上后，误差变成 1000 - fraction，变化量为 1000 - 2 * fraction。小数部分越大，改向上的误差增量越小。

因此选择最大的 up 个小数部分即可。若某个方案选了较小小数部分，却没选更大的，把两者的取整方向交换，向上数量不变，总和仍等于目标，而误差不会增加。这个交换论证保证了差值排序的最优性。

代码先累计全部向下的误差，再逐个加入被选候选的误差变化，始终使用整数精确计算。最后把千分位总误差拆成整数部分与三位小数，补齐前导零后输出。

解题步骤

1. 解析每个价格的整数部分和三位小数整数，累加 sumFloor 与全部向下的误差。
2. 只把非零小数部分加入候选列表，整数价格不占改向上的名额。
3. 计算 up，若不在 0..候选数量 之间，返回 "-1"。
4. 将候选按小数部分升序排序，选择末尾最大的 up 项，分别把 1000 - 2 * fraction 加到误差中。
5. 用除以 1000 的商与余数格式化输出，余数始终补足三位。

代码实现

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;
            }
        }

        // 每个非整数价格改为上取整，恰好使总和增加 1。
        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)
        }
    }

    // 每个非整数价格改为上取整，恰好使总和增加 1。
    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)
}

复杂度分析

• 时间复杂度：设非整数价格数为 u，时间为 $O(n+u\log(u+1))$，只排序有效候选。
• 空间复杂度：$O(n)$，保存候选小数部分。

关键点总结

[!green]

• 目标总和先确定向上次数，剩下的才是在固定名额内最小化误差。
• 选择依据是改变取整方向的误差差值，它随小数部分增大而减小。
• 固定三位小数可以全程转换成千分位整数，精确处理计算和格式。
• 即使某次向上会增加误差，也可能是达到目标必须占用的名额，不能擅自少选。

易错点总结

[!yellow]

• 把整数价格也列入可向上加一的候选，会误判目标可达范围。
• 对每项独立四舍五入，不一定让总和恰好等于目标。
• 选择小数部分较小的价格向上，会增加更大的误差，贪心方向相反。
• 只检查名额不足或过多的一侧，无法完整排除两类无解情况。
• Java 排序包含数组未填写的尾部，会把默认零当作候选；代码只排序实际有效前缀。
• 输出未补足三位小数，或解析时把三位小数当成浮点再反复运算，都会破坏题目要求的精确结果格式。

相似题目

题目	难度	关联与区别
1029. 两地调度	中等	同样先取全部选择一侧的基准，再按切换到另一侧的误差或费用差挑固定数量。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2022/75088297

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！