give >= need, the level mid is feasible; move l to mid and record ans = mid.

Otherwise move r to mid.

Repeat for sufficient iterations (e.g., 100) and return ans with the required precision.

Complexity

⏰ Time complexity: O(n * log(max(bucket))) (100 iterations, each O(n)).
🧺 Space complexity: O(1) (ignoring input/output).

Code

[{"language":"C++","code":"#include <vector>\n#include <algorithm>\nusing namespace std;\ndouble equalizeWater(vector<int>& buckets, int loss) {\n    double l = 0, r = *max_element(buckets.begin(), buckets.end()), ans = 0;\n    double eps = 1e-6;\n    double keep = 1 - loss / 100.0;\n    for (int iter = 0; iter < 100; ++iter) {\n        double mid = (l + r) / 2;\n        double need = 0, give = 0;\n        for (int x : buckets) {\n            if (x < mid) need += mid - x;\n            else give += (x - mid) * keep;\n        }\n        if (give >= need) {\n            ans = mid; l = mid;\n        } else {\n            r = mid;\n        }\n    }\n    return ans;\n}","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">#include</span><span style=\"color:#032F62;--shiki-dark:#9ECBFF\"> &#x3C;vector></span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">#include</span><span style=\"color:#032F62;--shiki-dark:#9ECBFF\"> &#x3C;algorithm></span></span>\n<

Related Tags