每日一题之智慧除草（滑动窗口，前缀和）

智能除草农业植保无人机作为最新的设备，可以加注除草剂进行除草。每次工作可以喷洒边长为K的正方形区域。
现有一块边长为N的正方形农田，将其分成N*N个方格单元，已知每个单元里的杂草数量。
求该植保无人机一次工作最多除草量和最少除草量的差值。
输入说明：第一行是2个正整数，分别为N和K（1≤K≤N≤1000）。之后N行N列正整数，表示每个单元中的杂草数量（不超过50）。
输出说明：该植保无人机一次工作最多除草量和最少除草量的差值。

输入样例：

4 2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

输出样例：

40

#include <iostream>  // 引入输入输出流库
#include <vector>    // 引入动态数组容器
#include <algorithm> // 引入算法库（例如 max 和 min）
using namespace std;

 // 计算给定区域的杂草总量（使用前缀和矩阵）
int get_sum(const vector<vector<int>>& prefix_sum, int x1, int y1, int x2, int y2) {
    // 计算矩形区域 (x1, y1) 到 (x2, y2) 的杂草总量
    return prefix_sum[x2 + 1][y2 + 1]  // 当前区域 (x2, y2) 的总和
           - prefix_sum[x1][y2 + 1]    // 减去上面多余的部分
           - prefix_sum[x2 + 1][y1]    // 减去左边多余的部分
           + prefix_sum[x1][y1];       // 加回左上角重复的部分
}

int main() {
    int N, K;
    cin >> N >> K; // 输入农田的大小 N 和需要计算的区域大小 K

    // 输入农田杂草数量矩阵
    vector<vector<int>> field(N, vector<int>(N)); // 创建一个 N x N 的二维数组来存储杂草数量
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> field[i][j]; // 读取每个位置的杂草数量
        }
    }

    // 构建前缀和矩阵
    vector<vector<int>> prefix_sum(N + 1, vector<int>(N + 1, 0)); // 创建一个 (N+1)x(N+1) 的前缀和矩阵，初始化为 0
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            // 根据前缀和公式填充 prefix_sum[i][j]
            prefix_sum[i][j] = field[i - 1][j - 1]  // 当前格子的杂草数量
                               + prefix_sum[i - 1][j] // 上方的区域和
                               + prefix_sum[i][j - 1] // 左侧的区域和
                               - prefix_sum[i - 1][j - 1]; // 左上角的重复区域要减去
        }
    }

    // 初始化最大值和最小值
    int max_grass = -1e9; // 初始化为一个非常小的值，用于寻找最大值
    int min_grass = 1e9;  // 初始化为一个非常大的值，用于寻找最小值

    // 遍历所有可能的 K x K 区域
    for (int i = 0; i <= N - K; ++i) { // i 从 0 到 N-K，确保 K x K 区域不会超出边界
        for (int j = 0; j <= N - K; ++j) { // j 从 0 到 N-K，确保 K x K 区域不会超出边界
            // 获取 (i, j) 到 (i+K-1, j+K-1) 区域内的杂草总量
            int total_grass = get_sum(prefix_sum, i, j, i + K - 1, j + K - 1);
            // 更新最大杂草总量
            max_grass = max(max_grass, total_grass);
            // 更新最小杂草总量
            min_grass = min(min_grass, total_grass);
        }
    }

    // 输出最大杂草总量与最小杂草总量的差
    cout << max_grass - min_grass << endl;

    return 0; // 程序执行完毕
}

经典二维矩阵前缀和，这道题是先计算好每一段的前缀和，然后去计算给定区域的前缀和

原文地址：https://blog.csdn.net/m0_73096516/article/details/143806968

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！