题目描述
你有 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 <= 1050 <= buckets[i] <= 1050 <= 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)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 | 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | 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
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | 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;
}
|