class Solution {
public:
double equalizeWater(vector<int>& buckets, int loss) {
}
};
2137. 通过倒水操作让所有的水桶所含水量相等
你有 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原站题解
java 解法, 执行用时: 142 ms, 内存消耗: 57.2 MB, 提交时间: 2023-10-21 23:07:01
class Solution {
public double equalizeWater(int[] buckets, int loss) {
double left = 0;
double right = 100000;
double r = 0.000001;
while(right-left>=r){
double mid = (left+right)/2.0;
double sum = 0;
for(int item:buckets){
if(item>mid){
sum+=((double)item-mid)*(100.0-(double)loss)/100.0;
}else{
sum-=mid-(double)item;
}
}
if(sum>0){
left = mid;
}else{
right = mid;
}
}
return left;
}
}
golang 解法, 执行用时: 124 ms, 内存消耗: 8.1 MB, 提交时间: 2023-10-21 23:06:37
func equalizeWater(buckets []int, loss int) float64 {
bs := make([]float64, len(buckets))
for i := 0; i < len(bs); i++ {
bs[i] = float64(buckets[i])
}
rate := float64(100-loss) / 100
check := func(m float64) bool {
var rest, need float64
for i := 0; i < len(bs); i++ {
if bs[i] > m {
rest += bs[i] - m
} else {
need += m - bs[i]
}
}
return rest*rate-need >= 1e-9
}
var l, h float64 = 0, 100000
for h-l > 1e-9 {
m := (h + l) / 2
if check(m) {
l = m
} else {
h = m
}
}
return l
}
cpp 解法, 执行用时: 260 ms, 内存消耗: 68.3 MB, 提交时间: 2023-10-21 23:06:14
class Solution {
public:
double equalizeWater(vector<int> &buckets, int loss) {
int n = buckets.size();
priority_queue<double> pq;
for (auto b : buckets)
pq.emplace(b);
double sum = accumulate(buckets.begin(), buckets.end(), 0.0);
double mean = sum / n;
auto t = pq.top();
while (t - mean > 1e-6) {
t=pq.top();
pq.pop();
pq.emplace(mean);
sum -= (t - mean) * loss / 100;
mean = sum / n;
}
return pq.top();
}
};
python3 解法, 执行用时: 996 ms, 内存消耗: 26.9 MB, 提交时间: 2023-10-21 23:05:40
class Solution:
def equalizeWater(self, buckets: List[int], loss: int) -> float:
n = len(buckets)
tot = sum(buckets)
l, r = 0, tot / n
eps = 10 ** (-6)
def check(x):
a = b = 0
for i in buckets:
if i >= x:
a += i - x
else:
b += (x - i) / (100 - loss) * 100
if a >= b:
return True
return False
while r - l > eps:
mid = (l + r) / 2
if check(mid):
l = mid
else:
r = mid
return r