Description#
You have n buckets each containing some gallons of water in it, represented by a 0-indexed integer array buckets, where the ith bucket contains buckets[i] gallons of water. You are also given an integer loss.
You want to make the amount of water in each bucket equal. You can pour any amount of water from one bucket to another bucket (not necessarily an integer). However, every time you pour k gallons of water, you spill loss percent of k.
Return the maximum amount of water in each bucket after making the amount of water equal. Answers within 10-5 of the actual answer will be accepted.
Example 1:
Input: buckets = [1,2,7], loss = 80
Output: 2.00000
Explanation: Pour 5 gallons of water from buckets[2] to buckets[0].
5 * 80% = 4 gallons are spilled and buckets[0] only receives 5 - 4 = 1 gallon of water.
All buckets have 2 gallons of water in them so return 2.
Example 2:
Input: buckets = [2,4,6], loss = 50
Output: 3.50000
Explanation: Pour 0.5 gallons of water from buckets[1] to buckets[0].
0.5 * 50% = 0.25 gallons are spilled and buckets[0] only receives 0.5 - 0.25 = 0.25 gallons of water.
Now, buckets = [2.25, 3.5, 6].
Pour 2.5 gallons of water from buckets[2] to buckets[0].
2.5 * 50% = 1.25 gallons are spilled and buckets[0] only receives 2.5 - 1.25 = 1.25 gallons of water.
All buckets have 3.5 gallons of water in them so return 3.5.
Example 3:
Input: buckets = [3,3,3,3], loss = 40
Output: 3.00000
Explanation: All buckets already have the same amount of water in them.
Constraints:
1 <= buckets.length <= 1050 <= buckets[i] <= 1050 <= loss <= 99
Solutions#
Solution 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;
}
|
