Leetcode3453.SeparateSquaresI

Leetcode 3453. Separate Squares I 1. 解题思路2. 代码实现 题目链接：3453. Separate Squares I 1. 解题思路

这一题思路上就是一个二分法，显然，随着y的增加，面积的增长是一个递增函数，因此，我们使用二分法找到最小的y使得其下方面积为总面积的一半即可。

而对于如何计算y下方的面积，这里我们只是暴力地做了一个循环遍历，首先将squares全部按照y坐标进行有序排列，然后计算一下所有起始位置在给定y下方的正方形的相应面积即可。

2. 代码实现

给出python代码实现如下：

class Solution: def separateSquares(self, squares: List[List[int]]) -> float: S = sum(l*l for x, y, l in squares) squares = sorted(squares, key=lambda x: (x[1], x[2])) def fn(y): s = 0 for xi, yi, li in squares: if yi >= y: break s += li * (min(yi+li, y) - yi) return s l, r = min(x[1] for x in squares), max(x[1]+x[2] for x in squares) while r-l > 1e-5: k = (l+r) / 2 s = fn(k) if s < S / 2: l = k else: r = k return r

提交代码评测得到：耗时3111ms，占用内存47.3MB。