【华为OD-E卷 - 95 光伏场地建设规划 100分（python、java、c++、js、c）

id="article_content" class="article_content clearfix" style="height: 2000px; overflow: hidden;"> id="content_views" class="markdown_views prism-tomorrow-night">

【华为OD-E卷 - 光伏场地建设规划 100分（python、java、c++、js、c）】

题目

祖国西北部有一片大片荒地，其中零星的分布着一些湖泊，保护区，矿区；
整体上常年光照良好，但是也有一些地区光照不太好。
某电力公司希望在这里建设多个光伏电站，生产清洁能源对每平方公里的土地进行了发电评估，其中不能建设的区域发电量为 0 kw，可以发电的区域根据光照，地形等给出了每平方公里年发电量 x 千瓦。
我们希望能够找到其中集中的矩形区域建设电站，能够获得良好的收益

输入描述

  • 第一行输入为调研的地区长，宽，以及准备建设的电站【长宽相等，为正方形】的边长，最低要求的发电量。

之后每行为调研区域每平方公里的发电量。

例如，输入为：

2 5 2 6 1 3 4 5 8 2 3 6 7 1

表示调研的区域大小为长 2 宽 5 的矩形，我们要建设的电站的边长为 2，建设电站最低发电量为 6

输出描述

  • 输出为这样的区域有多少个？

上述输入长度为 2 的正方形满足发电量大于等于 6 的区域有 4 个。则输出为：

4

用例

用例一：
输入：
2 5 2 6
1 3 4 5 8
2 3 6 7 1
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
  • 1
  • 2
  • 3
输出：
4
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
  • 1
用例二：
输入：
2 5 1 6
1 3 4 5 8
2 3 6 7 1
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
  • 1
  • 2
  • 3
输出：
3
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
用例三：
输入：
2 5 1 0
1 3 4 5 8
2 3 6 7 1
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
输出：
10
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

python解法

给定一个二维网格 grid，其大小为 m x n。
需要统计满足以下条件的子矩形的数量：
子矩形的大小为 side x side。
子矩形中所有元素的总和不小于 min_power。
解决方案

直接枚举：
遍历所有可能的子矩形的左上角位置 (i, j)。
计算以 (i, j) 为左上角，大小为 side x side 的矩形的元素总和。
如果总和大于或等于 min_power，则计数器 count 加 1。
优化计算：
枚举过程中，重复计算子矩形内的元素总和会导致效率低下。
使用 行前缀和 优化：
先计算每一行中长度为 side 的连续子数组的和。
再通过这些行前缀和计算矩形总和。

算法流程

初始化一个二维数组 row_sum，其中 row_sum[i][j] 表示网格中第 i 行从列 j 开始，长度为 side 的连续子数组的和。
遍历所有可能的子矩形左上角位置 (i, j)：
使用 row_sum 快速计算该矩形的总和。
如果总和大于或等于 min_power，计数器加 1。
输出计数器的值。

# 输入获取
m, n, side, min_power = map(int, input().split())  # 输入矩阵大小、子矩形边长和最小能量值
grid = [list(map(int, input().split())) for _ in range(m)]  # 输入网格矩阵

def count_valid_zones():
    # 初始化计数器
    count = 0
    
    # 计算每一行中宽度为 side 的连续子数组的前缀和
    row_sum = [[0] * n for _ in range(m)]  # 用于存储行前缀和的二维数组
    for i in range(m):
        for j in range(n - side + 1):  # 仅计算宽度为 side 的部分
            row_sum[i][j] = sum(grid[i][j:j + side])  # 计算每行的子数组和

    # 遍历所有可能的矩形左上角位置 (i, j)
    for i in range(m - side + 1):
        for j in range(n - side + 1):
            # 计算以 (i, j) 为左上角的 side x side 矩形的总和
            total = sum(row_sum[x][j] for x in range(i, i + side))
            
            # 如果总和大于等于 min_power，则计数器加 1
            if total >= min_power:
                count += 1
                
    return count

# 输出满足条件的矩形数量
print(count_valid_zones())

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

java解法

给定一个二维网格 grid（大小为 rows x cols），需要统计满足以下条件的子矩形的数量：
子矩形的大小为 size x size。
子矩形内的所有元素总和不小于 minSum。
解决方案

优化子矩形总和的计算：
直接计算每个子矩形的总和会导致重复计算，效率较低。
为了高效计算子矩形的总和，使用二维前缀和优化：
定义二维前缀和数组 prefixSum，其中 prefixSum[i][j] 表示从网格的左上角 (0, 0) 到 (i-1, j-1) 之间的所有元素总和。
对于任意一个子矩形，其左上角为 (i, j)，右下角为 (i+size-1, j+size-1)，可以通过前缀和快速计算总和。
步骤：
先预处理二维前缀和数组。
枚举所有可能的子矩形左上角位置 (i, j)。
使用前缀和公式快速计算子矩形的总和，并判断是否满足条件。
计数符合条件的子矩形

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 输入网格的行数和列数
        int r = sc.nextInt();
        int c = sc.nextInt();
        // 输入子矩形的边长和最小总和
        int len = sc.nextInt();
        int limit = sc.nextInt();

        // 输入网格的值
        int[][] grid = new int[r][c];
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                grid[i][j] = sc.nextInt();
            }
        }

        // 计算并输出符合条件的子矩形数量
        System.out.println(countValidStations(grid, r, c, len, limit));
    }

    /**
     * 统计满足条件的子矩形数量
     *
     * @param grid    输入网格
     * @param rows    网格的行数
     * @param cols    网格的列数
     * @param size    子矩形的边长
     * @param minSum  子矩形的最小总和
     * @return 符合条件的子矩形数量
     */
    public static int countValidStations(int[][] grid, int rows, int cols, int size, int minSum) {
        // 1. 构建二维前缀和数组
        int[][] prefixSum = new int[rows + 1][cols + 1]; // 多加一行和一列，用于简化计算

        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                // 计算前缀和：当前单元格的值 + 上方 + 左方 - 左上角重叠部分
                prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1]
                        - prefixSum[i - 1][j - 1] + grid[i - 1][j - 1];
            }
        }

        // 2. 遍历所有可能的子矩形，计算其总和并判断是否满足条件
        int count = 0; // 计数器
        for (int i = size; i <= rows; i++) { // 确保子矩形不会超出网格范围
            for (int j = size; j <= cols; j++) {
                // 计算子矩形的总和，公式：
                // 当前矩形总和 = 右下角 - 上方矩形 - 左方矩形 + 左上角重叠部分
                int sum = prefixSum[i][j]
                        - prefixSum[i - size][j]
                        - prefixSum[i][j - size]
                        + prefixSum[i - size][j - size];

                // 判断是否满足最小总和条件
                if (sum >= minSum) {
                    count++;
                }
            }
        }

        return count; // 返回符合条件的子矩形数量
    }
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

C++解法

更新中
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

C解法

更新中
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

JS解法

给定一个二维网格 grid，其大小为 rows x cols。
需要统计大小为 size x size 的所有子矩形（子网格）中，总和不小于给定阈值 threshold 的子矩形的数量。

算法流程

初始化二维前缀和矩阵 sumMatrix。
遍历所有可能的子矩形右下角位置 (row, col)，通过前缀和公式计算其总和。
检查总和是否满足条件，满足时计数器加 1。

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const getLine = async () => (await iter.next()).value;

void (async function () {
    // 读取输入的基本参数：行数、列数、子矩形大小和阈值
    const [rows, cols, size, threshold] = (await getLine()).split(" ").map(Number);

    // 读取网格数据
    const grid = [];
    for (let i = 0; i < rows; i++) {
        grid.push((await getLine()).split(" ").map(Number));
    }

    // 调用函数计算符合条件的子矩形数量并输出结果
    console.log(countSquares(rows, cols, size, threshold, grid));
})();

/**
 * 统计满足条件的子矩形数量
 *
 * @param {number} rows 网格的行数
 * @param {number} cols 网格的列数
 * @param {number} size 子矩形的边长
 * @param {number} threshold 子矩形的最小总和
 * @param {number[][]} grid 输入网格
 * @returns {number} 满足条件的子矩形数量
 */
function countSquares(rows, cols, size, threshold, grid) {
    // 初始化二维前缀和矩阵，多加一行和一列以简化边界处理
    const sumMatrix = Array.from({ length: rows + 1 }, () => Array(cols + 1).fill(0));

    // 构建二维前缀和
    for (let row = 1; row <= rows; row++) {
        for (let col = 1; col <= cols; col++) {
            sumMatrix[row][col] =
                grid[row - 1][col - 1] +
                sumMatrix[row - 1][col] +
                sumMatrix[row][col - 1] -
                sumMatrix[row - 1][col - 1];
        }
    }

    // 初始化计数器
    let result = 0;

    // 遍历所有可能的子矩形右下角位置
    for (let row = size; row <= rows; row++) {
        for (let col = size; col <= cols; col++) {
            // 使用前缀和公式计算当前子矩形的总和
            const totalPower =
                sumMatrix[row][col] -
                sumMatrix[row - size][col] -
                sumMatrix[row][col - size] +
                sumMatrix[row - size][col - size];

            // 如果总和满足条件，计数器加 1
            if (totalPower >= threshold) {
                result++;
            }
        }
    }

    // 返回符合条件的子矩形数量
    return result;
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏

注：本文转载自blog.csdn.net的CodeClimb的文章"https://blog.csdn.net/CodeClimb/article/details/145064448"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！