Skip to content

Latest commit

 

History

History
208 lines (173 loc) · 6.52 KB

README.md

File metadata and controls

208 lines (173 loc) · 6.52 KB

2137. 通过倒水操作让所有的水桶所含水量相等

English Version

题目描述

你有 n 个水桶，每个水桶中所含的水量用一个 下标从 0 开始 的数组 buckets 给出，第 i 个水桶中有 buckets[i] 升水。

你想让所有的水桶中所含的水量相同。你可以从一个水桶向其它任意一个水桶倒任意数量的水（可以不是整数）。但是，你每倒 k 升水，百分之 loss 的水会洒掉。

请返回经过倒水操作，所有水桶中的水量相同时，每个水桶中的 最大 水量。如果你的答案和标准答案的误差不超过 10-5，那么答案将被通过。

 

示例 1:

输入: buckets = [1,2,7], loss = 80
输出: 2.00000
解释: 从水桶 2 向水桶 0 倒 5 升水。
5 * 80% = 4 升水会洒掉，水桶 0 只会获得 5 - 4 = 1 升水。
此时所有的水桶中都含有 2 升水，所以返回 2。

示例 2:

输入: buckets = [2,4,6], loss = 50
输出: 3.50000
解释: 从水桶 1 向水桶 0 倒 0.5 升水。
0.5 * 50% = 0.25 升水会洒掉，水桶 0 只会获得 0.5 - 0.25 = 0.25 升水。
此时, buckets = [2.25, 3.5, 6].

从水桶 2 向水桶 0 倒 2.5 升水。
2.5 * 50% = 1.25 升水会洒掉，水桶 0 只会获得 2.5 - 1.25 = 1.25 升水。
此时所有的水桶中都含有 3.5 升水，所以返回 3.5。

示例 3:

输入: buckets = [3,3,3,3], loss = 40
输出: 3.00000
解释: 所有的水桶已经含有相同的水量。

 

提示:

  • 1 <= buckets.length <= 105
  • 0 <= buckets[i] <= 105
  • 0 <= loss <= 99

解法

方法一：二分查找（浮点数二分）

我们注意到，如果一个水量 $x$ 满足条件，那么所有小于 $x$ 的水量也满足条件。因此我们可以使用二分查找的方法找到最大的满足条件的水量。

我们定义二分查找的左边界 $l=0$，右边界 $r=\max(buckets)$。每次二分查找时，我们取 $l$ 和 $r$ 的中点 $mid$，判断 $mid$ 是否满足条件。如果满足条件，那么我们将 $l$ 更新为 $mid$，否则我们将 $r$ 更新为 $m$。在二分查找结束后，最大的满足条件的水量即为 $l$。

问题的关键转换为如果判断一个水量 $v$ 是否满足条件。我们可以遍历所有水桶，对于每个水桶，如果其水量大于 $v$，那么需要倒出 $x-v$ 的水量；如果其水量小于 $v$，那么需要向其中倒入 $(v-x)\times\frac{100}{100-\textit{loss}}$ 的水量。如果倒出的水量大于等于倒入的水量，那么说明 $v$ 满足条件。

时间复杂度 $O(n \times \log M)$，其中 $n$ 和 $M$ 分别是数组 $buckets$ 的长度和最大值。二分查找的时间复杂度为 $O(\log M)$，每次二分查找需要遍历数组 $buckets$，时间复杂度为 $O(n)$。空间复杂度 $O(1)$。

class Solution:
    def equalizeWater(self, buckets: List[int], loss: int) -> float:
        def check(v):
            a = b = 0
            for x in buckets:
                if x >= v:
                    a += x - v
                else:
                    b += (v - x) * 100 / (100 - loss)
            return a >= b

        l, r = 0, max(buckets)
        while r - l > 1e-5:
            mid = (l + r) / 2
            if check(mid):
                l = mid
            else:
                r = mid
        return l
class Solution {
    public double equalizeWater(int[] buckets, int loss) {
        double l = 0, r = Arrays.stream(buckets).max().getAsInt();
        while (r - l > 1e-5) {
            double mid = (l + r) / 2;
            if (check(buckets, loss, mid)) {
                l = mid;
            } else {
                r = mid;
            }
        }
        return l;
    }

    private boolean check(int[] buckets, int loss, double v) {
        double a = 0;
        double b = 0;
        for (int x : buckets) {
            if (x > v) {
                a += x - v;
            } else {
                b += (v - x) * 100 / (100 - loss);
            }
        }
        return a >= b;
    }
}
class Solution {
public:
    double equalizeWater(vector<int>& buckets, int loss) {
        double l = 0, r = *max_element(buckets.begin(), buckets.end());
        auto check = [&](double v) {
            double a = 0, b = 0;
            for (int x : buckets) {
                if (x > v) {
                    a += x - v;
                } else {
                    b += (v - x) * 100 / (100 - loss);
                }
            }
            return a >= b;
        };
        while (r - l > 1e-5) {
            double mid = (l + r) / 2;
            if (check(mid)) {
                l = mid;
            } else {
                r = mid;
            }
        }
        return l;
    }
};
func equalizeWater(buckets []int, loss int) float64 {
	check := func(v float64) bool {
		var a, b float64
		for _, x := range buckets {
			if float64(x) >= v {
				a += float64(x) - v
			} else {
				b += (v - float64(x)) * 100 / float64(100-loss)
			}
		}
		return a >= b
	}

	l, r := float64(0), float64(slices.Max(buckets))
	for r-l > 1e-5 {
		mid := (l + r) / 2
		if check(mid) {
			l = mid
		} else {
			r = mid
		}
	}
	return l
}
function equalizeWater(buckets: number[], loss: number): number {
    let l = 0;
    let r = Math.max(...buckets);
    const check = (v: number): boolean => {
        let [a, b] = [0, 0];
        for (const x of buckets) {
            if (x >= v) {
                a += x - v;
            } else {
                b += ((v - x) * 100) / (100 - loss);
            }
        }
        return a >= b;
    };
    while (r - l > 1e-5) {
        const mid = (l + r) / 2;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid;
        }
    }
    return l;
}