LeetCode 3453.分割正方形 I：二分查找

【LetMeFly】3453.分割正方形 I：二分查找

力扣题目链接：https://leetcode.cn/problems/separate-squares-i/

给你一个二维整数数组squares，其中squares[i] = [xi, yi, li]表示一个与 x 轴平行的正方形的左下角坐标和正方形的边长。

找到一个最小的y 坐标，它对应一条水平线，该线需要满足它以上正方形的总面积等于该线以下正方形的总面积。

答案如果与实际答案的误差在10-5以内，将视为正确答案。

注意：正方形可能会重叠。重叠区域应该被多次计数。

示例 1：

输入：squares = [[0,0,1],[2,2,1]]

输出：1.00000

解释：

任何在y = 1和y = 2之间的水平线都会有 1 平方单位的面积在其上方，1 平方单位的面积在其下方。最小的 y 坐标是 1。

示例 2：

输入：squares = [[0,0,2],[1,1,1]]

输出：1.16667

解释：

面积如下：

• 线下的面积：7/6 * 2 (红色) + 1/6 (蓝色) = 15/6 = 2.5。
• 线上的面积：5/6 * 2 (红色) + 5/6 (蓝色) = 15/6 = 2.5。

由于线以上和线以下的面积相等，输出为7/6 = 1.16667。

提示：

• 1 <= squares.length <= 5 * 104
• squares[i] = [xi, yi, li]
• squares[i].length == 3
• 0 <= xi, yi<= 109
• 1 <= li<= 109
• 所有正方形的总面积不超过1012。

解题方法：二分查找

先算下所有正方形的总面积，然后二分分割线高度，太低就高点太高就低点。

终止条件：两次计算结果分割线移动返回不超过10 − 5 10^{-5}10−5或直接进行50 5050次求值。

>>>10**9/2**461.4210854715202004e-05>>>10**9/2**477.105427357601002e-06

• 时间复杂度O ( C × l e n ( s q u a r e s ) ) O(C\times len(squares))O(C×len(squares))，其中C = 50 C=50C=50或C = log ⁡ 2 m a x ( s q u i r e s [ i ] [ 1 ] ) − m i n ( s q u i r e s [ i ] [ 1 ] ) C=\log_2{max(squires[i][1])-min(squires[i][1])}C=log2​max(squires[i][1])−min(squires[i][1])
• 空间复杂度O ( 1 ) O(1)O(1)

AC代码

C++

/* * @LastEditTime: 2026-01-13 22:21:20 */classSolution{private:doublehalf=0;vector<vector<int>>squares;boolcheck(doubleh){doubletotal=0;for(vector<int>&s:squares){doublefrom=max(double(s[1]),h);doubleto=s[1]+s[2];total+=max(0.,(to-from)*s[2]);}returntotal>half;}public:doubleseparateSquares(vector<vector<int>>&squares){longlongtotal=0;// !!!!!记得初始化for(vector<int>&s:squares){total+=((longlong)s[2])*s[2];}this->squares=move(squares);half=1.*total/2;doublel=0,r=1000000000;for(int_=0;_<50;_++){doublemid=(l+r)/2;if(check(mid)){l=mid;}else{r=mid;}}returnl;}};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源