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

Categories:

题目描述
思路分析
1. 解法一：贪心选择上取整（推荐）
相似题目

题目描述

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

思路分析

解法一：贪心选择上取整（推荐）

核心思路：

先全部取下取整，得到最小和 sumFloor。

需要补的差值 diff = target - sumFloor 必须在可上取整数量范围内。

选择小数部分最大的 diff 项上取整，使误差最小。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示价格数量。

空间复杂度：O(n)，存储小数部分。

import java.util.*;

class Solution {
    public String minimizeError(String[] prices, int target) {
        List<Double> frac = new ArrayList<>();
        int sumFloor = 0;

        for (String s : prices) {
            double v = Double.parseDouble(s);
            int f = (int) Math.floor(v);
            sumFloor += f;
            if (v - f > 0) {
                frac.add(v - f);
            }
        }

        int diff = target - sumFloor;
        if (diff < 0 || diff > frac.size()) {
            return "-1";
        }

        frac.sort(Collections.reverseOrder());
        double error = 0.0;
        for (double f : frac) {
            error += f;
        }
        for (int i = 0; i < diff; i++) {
            error += 1 - 2 * frac.get(i);
        }

        return String.format("%.3f", error);
    }
}

import (
    "fmt"
    "math"
    "sort"
    "strconv"
)

func minimizeError(prices []string, target int) string {
    frac := make([]float64, 0)
    sumFloor := 0

    for _, s := range prices {
        v, _ := strconv.ParseFloat(s, 64)
        f := int(math.Floor(v))
        sumFloor += f
        if v-float64(f) > 0 {
            frac = append(frac, v-float64(f))
        }
    }

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

    sort.Slice(frac, func(i, j int) bool { return frac[i] > frac[j] })
    error := 0.0
    for _, f := range frac {
        error += f
    }
    for i := 0; i < diff; i++ {
        error += 1 - 2*frac[i]
    }

    return fmt.Sprintf("%.3f", error)
}

相似题目

题目	难度	考察点
857. 雇佣 K 名工人的最低成本	困难	贪心
1353. 最多可以参加的会议数目	中等	贪心
948. 令牌放置	中等	贪心
1058. 最小化舍入误差以满足目标	中等	贪心
1642. 可以到达的最远建筑	中等	贪心 + 堆

本文作者: HGNULB

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