LeetCode-in-Java/src/main/java/g3401_3500/s3453_separate_squares_i/Solution.java at 7fe7f8d33d27d6c36cf437f62aa23a0a4061c3a6 · jscrdev/LeetCode-in-Java · GitHub

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
28
29
30
31
32
33
34
package g3401_3500.s3453_separate_squares_i;

// #Medium #Array #Binary_Search #2025_02_18_Time_60_ms_(99.96%)_Space_88.58_MB_(26.92%)

public class Solution {
    public double separateSquares(int[][] squares) {
        long hi = 0L;
        long lo = 1_000_000_000L;
        for (int[] q : squares) {
            lo = Math.min(lo, q[1]);
            hi = Math.max(hi, q[1] + (long) q[2]);
        }
        while (lo <= hi) {
            long mid = (lo + hi) / 2;
            if (diff(mid, squares) <= 0) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        double diff1 = diff(hi, squares);
        double diff2 = diff(lo, squares);
        return hi + diff1 / (diff1 - diff2);
    }

    private double diff(long mid, int[][] squares) {
        double[] res = new double[2];
        for (int[] q : squares) {
            res[0] += Math.min(q[2], Math.max(0, mid - q[1])) * q[2];
            res[1] += Math.min(q[2], Math.max(0, q[1] + q[2] - mid)) * q[2];
        }
        return res[1] - res[0];
    }
}