Question

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