3453. 分割正方形 I

思路

先計算出總面積，再去二分查找答案。
查找的次數越多，精度就越高。

程式碼

二分查找

class Solution {
public:
    double separateSquares(vector<vector<int>>& squares) {
        double sum = 0;
        double low = 1e9, high = 0; // y 的最低跟最高位置
        for(auto& s : squares) {
            low = min(low, (double)s[1]);
            high = max(high, (double)(s[1] + s[2]));
            sum += (double)s[2] * s[2];
        }
        sum /= 2;

        auto getArea = [&](double k) -> double { // 給定 y, 找到線上的面積一共多少。
            double area = 0;
            for(auto& s : squares) {
                if(k <= s[1]) continue;
                if(k >= s[1] + s[2]) {
                    area += (double)s[2] * s[2];
                }
                else {
                    area += (double)s[2] * (k - s[1]);
                }
            }
            return area;
        };
        
        for(int i = 0; i < 50; ++i) {
            double mid = low + (high - low) / 2.0;
            if(getArea(mid) < sum) {
                low = mid;
            }
            else {
                high = mid;
            }
        }
        return low;
    }
};

複雜度分析

• 時間複雜度：$O(n^2)$
• 空間複雜度：$O(1)$