【Leetcode Daily】3453分割正方形I

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个二维数组，代表一个二维坐标系上有很多矩阵，现在可以画一个横线，求这个横线能恰好平分上下的正方形面积的高度（y 值）

思路分享

• 没想到是二分答案，而且由于题目要求精度为 10^5 所以可以对于每个面积的计算乘 10**5 化为整数，然后从下往上，二分去逼近这个答案。

  https://leetcode.cn/problems/separate-squares-i/solutions/3076424/zheng-shu-er-fen-pythonjavacgo-by-endles-8yn5/?envType=daily-question&envId=2026-01-13

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution:
    def separateSquares(self, squares: List[List[int]]) -> float:
        M = 100_000
        total_area = sum(l*l for _, _, l in squares)

        def check(multi_y: int) -> bool:
            area = 0
            for _, y, l in squares:
                if y * M < multi_y:
                    area += l * min(multi_y -  y * M, l * M)
            return area * 2 >= total_area * M 
        
        max_y = max(y+l for _,y, l in squares)
        return bisect_left(range(max_y*M), True, key=check) / M