方伯伯浇水2 - 用前缀和优化解决玉米田浇水问题

方伯伯浇水2 - 用前缀和优化解决玉米田浇水问题

题目描述

方伯伯有一块玉米田，玉米田可以视为平面直角坐标系上横纵坐标在 -10^5 至 10^5 范围内（包括边界）的一片正方形区域。玉米田内的每个整点（横纵坐标均为整数的点）上都种着一株玉米。

方伯伯连续 m 天对玉米田进行浇水，每天他会选出一个圆心坐标为 (x,y)，半径为 r 的圆形区域，对其中（不包括边界）的每株玉米浇一次水（如果圆形区域超过玉米田边界，超过部分无需浇水）。最开始所有玉米的品质都是 1，每次浇水会让该株玉米的品质增 1。

m 天过后，到了收获的季节，方伯伯想采用抽样检测的方式来调查玉米田的品质。方伯伯给出了 10 株玉米的坐标，他想调查这 10 株玉米品质的平均数。

输入格式

第一行输入一个正整数 m（m≤10^5），代表浇水天数。 接下来 m 行，每行输入三个整数 x_i,y_i（-10^5≤ x_i,y_i≤ 10^5）和 r_i（0 < r_i≤10^5），代表第 i 天浇水的圆形区域。

接下来 10 行，每行输入两个整数 x_i,y_i（-10^5≤ x_i,y_i≤ 10^5），代表收获季节调查的 10 株玉米的坐标。

输出格式

输出一个数字（保留 2 位小数），代表调查的这 10 株玉米品质的平均数。

样例 #1

样例输入 #1

2
3 4 5
-1 0 1
-1 0
0 0
1 0
2 0
3 0
-1 -1
0 -1
1 -1
2 -1
3 -1

样例输出 #1

1.40

提示

判断点 (x_1,y_1) 与圆 (x_0,y_0,r_0) 的方法是：

计算点 (x_1,y_1) 到圆心 (x_0,y_0) 的距离的平方 d^2=(x_1-x_0)^2+(y_1-y_0)^2，将这个值与圆的半径的平方 r_0^2 作比较：

• 如果 d^2< r_0^2，说明点在圆内；
• 如果 d^2= r_0^2，说明点在圆上；
• 如果 d^2> r_0^2，说明点在圆外。

算法分析

算法1：暴力模拟

对于每一天浇水，遍历所有的玉米，判断是否在圆形区域内，如果在则品质加1。

对于每一株需要调查的玉米，直接输出品质即可。

时间复杂度 O(mn)，其中 n 为玉米数量，过不了本题。

算法2：前缀和优化

对于每一天浇水，不需要遍历所有的玉米，可以通过前缀和优化。

首先，需要统计出每个位置的玉米数量，可以使用二维前缀和进行预处理。

然后，对于每一天浇水，可以计算出圆形区域内的左上角和右下角位置，再利用二维前缀和计算圆形区域内的玉米数量，最后将圆形区域内的所有玉米品质加1。

对于每一株需要调查的玉米，可以直接查询其品质。

时间复杂度 O(m+n log n)，其中 n 为玉米数量，可以通过本题。

C++ 代码

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

const int MAXN = 2e5 + 5;

int m, x, y, r, sum[MAXN][MAXN], corn[MAXN][MAXN];

int main() {
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> x >> y >> r;
        // 计算圆形区域的左上角和右下角坐标
        int left = max(x - r, -100000), right = min(x + r, 100000);
        int top = max(y - r, -100000), bottom = min(y + r, 100000);
        // 用二维前缀和计算圆形区域内的玉米数量
        int count = sum[right + 1][bottom + 1] - sum[left][bottom + 1] - sum[right + 1][top] + sum[left][top];
        // 将圆形区域内的所有玉米品质加 1
        for (int j = left; j <= right; j++) {
            for (int k = top; k <= bottom; k++) {
                if ((j - x) * (j - x) + (k - y) * (k - y) < r * r) {
                    corn[j + 100001][k + 100001]++;
                }
            }
        }
    }
    // 计算二维前缀和
    for (int i = 1; i <= MAXN; i++) {
        for (int j = 1; j <= MAXN; j++) {
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + corn[i][j];
        }
    }
    double avg = 0.0;
    for (int i = 0; i < 10; i++) {
        cin >> x >> y;
        // 查询玉米品质
        avg += corn[x + 100001][y + 100001] + 1;
    }
    printf('%.2lf
', avg / 10.0);
    return 0;
}

代码解析

1. 使用二维数组 corn 存储每个位置的玉米品质，使用二维数组 sum 存储二维前缀和。
2. 循环遍历每个浇水天数，计算圆形区域的左上角和右下角坐标，使用二维前缀和计算圆形区域内的玉米数量，最后将圆形区域内的所有玉米品质加 1。
3. 计算二维前缀和。
4. 循环遍历每个需要调查的玉米坐标，查询其品质，并累加到 avg 变量中。
5. 最后输出平均品质，保留两位小数。

总结

本题使用前缀和优化算法，可以高效地解决玉米田浇水问题。前缀和优化是一种常用的技巧，可以有效地降低时间复杂度。