问题分析

本题要求在一个 $1025×1025$ 的网格中，根据给定的毒气弹威力$d$和老鼠群体的位置及规模信息，找到一个爆炸位置，使得该位置毒气扩散区域内消灭的老鼠数量最多。若有多个最佳位置，选择$x$坐标最小，若$x$坐标相同则选择$y$ 坐标最小的位置。

解题思路

构建二维前缀和数组：创建一个二维数组 prefixSum，用于存储每个网格点及其左上角区域内老鼠数量的总和。遍历所有老鼠群体，将其数量累加到对应的网格点上，然后通过前缀和的计算方式，得到每个网格点的前缀和。计算扩散区域内老鼠总数：对于每个可能的爆炸位置$(x 0,y 0)$，根据毒气弹的威力$d$，利用前缀和数组来快速计算其扩散区域内老鼠的总数。具体计算方法是通过计算扩散区域四个角点的前缀和差值来得到。更新最佳位置：与之前一样，记录下消灭老鼠总数最大的位置，若有多个位置消灭的老鼠总数相同，选择x坐标最小，若x坐标相同则选择y坐标最小的位置。 输出结果：输出最佳位置的x、y坐标和消灭的老鼠总数 cpp# #include #include #include

using namespace std;

// 定义老鼠群体的结构体 struct RatGroup { int x, y, size; };

// 计算在 (x0, y0) 位置爆炸时消灭的老鼠总数 int calculateKilledRats(const vector& ratGroups, int x0, int y0, int d) { int total = 0; for (const auto& ratGroup : ratGroups) { int dx = abs(ratGroup.x - x0); int dy = abs(ratGroup.y - y0); if (max(dx, dy) <= d) { total += ratGroup.size; } } return total; }

int main() { int T; cin >> T;

while (T--) {
    int d, n;
    cin >> d >> n;

    vector<RatGroup> ratGroups(n);
    for (int i = 0; i < n; ++i) {
        cin >> ratGroups[i].x >> ratGroups[i].y >> ratGroups[i].size;
    }

    int bestX = 0, bestY = 0, maxKilled = 0;
    // 枚举所有可能的爆炸位置
    for (int x0 = 0; x0 <= 1024; ++x0) {
        for (int y0 = 0; y0 <= 1024; ++y0) {
            int killed = calculateKilledRats(ratGroups, x0, y0, d);
            if (killed > maxKilled || (killed == maxKilled && (x0 < bestX || (x0 == bestX && y0 < bestY)))) {
                maxKilled = killed;
                bestX = x0;
                bestY = y0;
            }
        }
    }

    cout << bestX << " " << bestY << " " << maxKilled << endl;
}

return 0;

}