最强祝福力场

发布时间 : 2025-12-29 16:59

最强祝福力场
小扣在探索丛林的过程中，无意间发现了传说中“落寞的黄金之都”。而在这片建筑废墟的地带中，小扣使用探测仪监测到了存在某种带有「祝福」效果的力场。经过不断的勘测记录，小扣将所有力场的分布都记录了下来。forceField[i] = [x,y,side] 表示第 i 片力场将覆盖以坐标 (x,y) 为中心，边长为 side 的正方形区域。

若任意一点的 力场强度 等于覆盖该点的力场数量，请求出在这片地带中 力场强度 最强处的 力场强度。

注意：

力场范围的边缘同样被力场覆盖。
1 <= forceField.length <= 100
forceField[i].length == 3
0 <= forceField[i][0], forceField[i][1] <= 10^9
1 <= forceField[i][2] <= 10^9

对于不是整数的边长，考虑放大两倍都变成整数。
矩形面积数值很大但是个数很少，而答案求的是覆盖最多的次数，所以只和它们的相对位置关系有关，考虑离散化。将它们的坐标从小到大从1开始映射，然后再求差分。

class Solution {
public:
    int fieldOfGreatestBlessing(vector<vector<int>>& f) {
        int n = f.size();
        set<long long> sx,sy;
        for(int i = 0; i < n; i++) {
            sx.insert((long long)f[i][0]*2 - f[i][2]);
            sx.insert((long long)f[i][0]*2 + f[i][2]);
            sy.insert((long long)f[i][1]*2 - f[i][2]);
            sy.insert((long long)f[i][1]*2 + f[i][2]);
        }
        map<long long,int> mx,my;
        int cnt = 1;
        for(auto& i : sx) {
            mx[i] = cnt++;
        }
        int row = cnt-1;
        cnt = 1;
        for(auto& i : sy) {
            my[i] = cnt++;
        }
        int col = cnt-1;
        int sum[row+2][col+2];
        memset(sum,0,sizeof(sum));
        for(int i = 0; i < n; i++) {
            long long x1 = (long long)f[i][0] *2 - f[i][2];
            long long y1 = (long long)f[i][1] *2 - f[i][2];
            long long x2 = (long long)f[i][0] *2 + f[i][2];
            long long y2 = (long long)f[i][1] *2 + f[i][2];
            x1 = mx[x1],x2 = mx[x2];
            y1 = my[y1],y2 = my[y2];
            sum[x1][y1]++;
            sum[x2+1][y2+1]++;
            sum[x2+1][y1]--;
            sum[x1][y2+1]--;
        }
        int ans = 0;
        for(int i = 1; i <= row; i++) {
            for(int j = 1; j <= col; j++) {
                sum[i][j] += sum[i-1][j] + sum[i][j-1] -sum[i-1][j-1];
                ans = max(ans,sum[i][j]);
            }
        }
        return ans;
    }
};