华为OD机试 - 荒地建设电站 - 滑动窗口（Python/JS/C/C++ 2024 E卷 200分）

9 阅读 0 评论 0 点赞

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

祖国西北部有一片大大的荒地，其中零星的分布着一些湖泊、保护区、矿区；

整体上光照良好，但是也有一些地区光照不太好。

某电力公司希望在这里建设多个光伏电站，并考察清洁能源对每平方公里的土地进行了发电评估，其中不能建设的区域发电量为0kw，可以发电的区域根据光照、地形等条件给出了每平方公里年发电量x千瓦。

我们希望能够找到其中集中且矩形区域建设电站，能够获得良好的收益。

二、输入描述

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

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

三、输出描述

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

四、测试用例

测试用例1：

1、输入

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

2、输出

3、说明

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

测试用例2：

1、输入

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

2、输出

3、说明

发电量阈值：T=30。

所有可能的 2x2 子区域及其发电量总和：

1 + 2 + 4 + 5 = 12 < 30
2 + 3 + 5 + 6 = 16 < 30
4 + 5 + 7 + 8 = 24 < 30
5 + 6 + 8 + 9 = 28 < 30

满足条件的子区域数量：0

五、解题思路

题目要求在一个 L x W 的矩形区域中，找到所有边长为 K 的正方形子区域，这些子区域的发电量总和至少为给定的阈值 T。为了高效地计算多个子区域的发电量总和，我们可以采用二维前缀和的数据结构。使用二维前缀和，可以在常数时间内计算任意 K x K 子矩形区域的总和，从而提高整体算法的效率。

1、为什么采用滑动窗口？

通过遍历所有可能的 K x K 子区域，结合前缀和快速计算其总和，从而判断是否满足条件。

相较于暴力计算每个子区域的总和，前缀和大幅减少了重复计算，提高了整体效率。

2、具体步骤：

输入处理：
- 读取第一行，获取 L（长度）、W（宽度）、K（正方形边长）和 T（发电量阈值）。
- 读取接下来的 L 行，每行包含 W 个整数，表示每平方公里的发电量，存储到二维数组 grid 中。
构建二维前缀和数组：
- 初始化一个 (L+1) x (W+1) 的前缀和数组 prefixSum，其中 prefixSum[i][j] 表示从 (0,0) 到 (i-1,j-1) 的子矩形区域的发电量总和。
- 使用动态规划的方法填充 prefixSum 数组。
遍历所有可能的 K x K 子区域并计数：
- 遍历所有可能的子区域右下角位置 (i,j)，计算该子区域的发电量总和。
- 如果总和大于等于阈值 T，则计数器加一。
输出结果：
- 最后输出满足条件的 K x K 子区域的数量。

六、Python算法源码

# 导入 sys 模块以读取输入
import sys

def main():
    # 读取所有输入并按空白字符分割
    input = sys.stdin.read().split()
    # 初始化一个指针来遍历输入列表
    ptr = 0
    
    # 读取 L（长度）
    L = int(input[ptr])
    ptr += 1
    # 读取 W（宽度）
    W = int(input[ptr])
    ptr += 1
    # 读取 K（正方形边长）
    K = int(input[ptr])
    ptr += 1
    # 读取 threshold（发电量阈值）
    threshold = int(input[ptr])
    ptr += 1
    
    # 初始化发电量网格 grid，大小为 L x W
    grid = []
    for i in range(L):
        row = []
        for j in range(W):
            # 读取每个发电量并添加到当前行
            row.append(int(input[ptr]))
            ptr += 1
        grid.append(row)
    
    # 初始化二维前缀和数组 prefixSum，大小为 (L+1) x (W+1)
    prefixSum = [[0] * (W + 1) for _ in range(L + 1)]
    
    # 填充前缀和数组
    for i in range(1, L + 1):
        for j in range(1, W + 1):
            # 计算当前位置的前缀和
            prefixSum[i][j] = grid[i - 1][j - 1] \
                              + prefixSum[i - 1][j] \
                              + prefixSum[i][j - 1] \
                              - prefixSum[i - 1][j - 1]
    
    # 初始化计数器
    count = 0
    # 遍历所有可能的 KxK 子区域
    for i in range(K, L + 1):
        for j in range(K, W + 1):
            # 计算当前 KxK 子区域的总发电量
            total = prefixSum[i][j] \
                    - prefixSum[i - K][j] \
                    - prefixSum[i][j - K] \
                    + prefixSum[i - K][j - K]
            # 如果总发电量满足条件，计数器加一
            if total >= threshold:
                count += 1
    
    # 输出最终结果
    print(count)

# 调用主函数
if __name__ == "__main__":
    main()

七、JavaScript算法源码

// 使用标准输入读取数据
const readline = require('readline');

// 创建接口以逐行读取输入
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

// 初始化一个数组来存储所有输入
const input = [];

// 监听每一行输入
rl.on('line', (line) => {
    // 将每行按空白字符分割并添加到 input 数组
    input.push(...line.trim().split(/\s+/));
});

// 当输入结束时执行主逻辑
rl.on('close', () => {
    let ptr = 0; // 初始化指针
    
    // 读取 L（长度）
    const L = parseInt(input[ptr++]);
    // 读取 W（宽度）
    const W = parseInt(input[ptr++]);
    // 读取 K（正方形边长）
    const K = parseInt(input[ptr++]);
    // 读取 threshold（发电量阈值）
    const threshold = parseInt(input[ptr++]);
    
    // 初始化发电量网格 grid，大小为 L x W
    const grid = [];
    for (let i = 0; i < L; i++) {
        const row = [];
        for (let j = 0; j < W; j++) {
            // 读取每个发电量并添加到当前行
            row.push(parseInt(input[ptr++]));
        }
        grid.push(row);
    }
    
    // 初始化二维前缀和数组 prefixSum，大小为 (L+1) x (W+1)
    const prefixSum = Array.from({length: L + 1}, () => Array(W + 1).fill(0));
    
    // 填充前缀和数组
    for (let i = 1; i <= L; i++) {
        for (let j = 1; j <= W; j++) {
            // 计算当前位置的前缀和
            prefixSum[i][j] = grid[i - 1][j - 1] 
                              + prefixSum[i - 1][j] 
                              + prefixSum[i][j - 1] 
                              - prefixSum[i - 1][j - 1];
        }
    }
    
    let count = 0; // 初始化计数器
    // 遍历所有可能的 KxK 子区域
    for (let i = K; i <= L; i++) {
        for (let j = K; j <= W; j++) {
            // 计算当前 KxK 子区域的总发电量
            const total = prefixSum[i][j]
                        - prefixSum[i - K][j]
                        - prefixSum[i][j - K]
                        + prefixSum[i - K][j - K];
            // 如果总发电量满足条件，计数器加一
            if (total >= threshold) {
                count++;
            }
        }
    }
    
    // 输出最终结果
    console.log(count);
});

八、C算法源码

#include <stdio.h>

// 主函数
int main() {
    int L, W, K, threshold;
    
    // 读取 L（长度）、W（宽度）、K（正方形边长）、threshold（发电量阈值）
    scanf("%d %d %d %d", &L, &W, &K, &threshold);
    
    // 定义发电量网格 grid，最大尺寸为 1000x1000（根据题目实际需求调整）
    // 为简单起见，这里假设 L 和 W 不超过 1000
    int grid[1000][1000];
    
    // 读取发电量数据
    for(int i = 0; i < L; i++) {
        for(int j = 0; j < W; j++) {
            scanf("%d", &grid[i][j]);
        }
    }
    
    // 定义二维前缀和数组 prefixSum，大小为 (L+1)x(W+1)
    // 初始化为 0
    long long prefixSum[L+1][W+1];
    for(int i = 0; i <= L; i++) {
        for(int j = 0; j <= W; j++) {
            prefixSum[i][j] = 0;
        }
    }
    
    // 计算前缀和
    for(int i = 1; i <= L; i++) {
        for(int j = 1; j <= W; j++) {
            prefixSum[i][j] = grid[i-1][j-1]
                             + prefixSum[i-1][j]
                             + prefixSum[i][j-1]
                             - prefixSum[i-1][j-1];
        }
    }
    
    int count = 0; // 初始化计数器
    
    // 遍历所有可能的 KxK 子区域
    for(int i = K; i <= L; i++) {
        for(int j = K; j <= W; j++) {
            // 计算当前 KxK 子区域的总发电量
            long long total = prefixSum[i][j]
                             - prefixSum[i-K][j]
                             - prefixSum[i][j-K]
                             + prefixSum[i-K][j-K];
            // 如果总发电量满足条件，计数器加一
            if(total >= threshold) {
                count++;
            }
        }
    }
    
    // 输出最终结果
    printf("%d\n", count);
    
    return 0;
}

九、C++算法源码

#include <iostream>
#include <vector>
using namespace std;

int main(){
    ios::sync_with_stdio(false); // 关闭同步，加快输入速度
    cin.tie(0); // 取消 cin 与 cout 的绑定
    
    int L, W, K, threshold;
    
    // 读取 L（长度）、W（宽度）、K（正方形边长）、threshold（发电量阈值）
    cin >> L >> W >> K >> threshold;
    
    // 定义发电量网格 grid，使用二维向量
    vector<vector<int>> grid(L, vector<int>(W));
    
    // 读取发电量数据
    for(int i = 0; i < L; i++) {
        for(int j = 0; j < W; j++) {
            cin >> grid[i][j];
        }
    }
    
    // 定义二维前缀和数组 prefixSum，大小为 (L+1)x(W+1)
    vector<vector<long long>> prefixSum(L+1, vector<long long>(W+1, 0));
    
    // 计算前缀和
    for(int i = 1; i <= L; i++) {
        for(int j = 1; j <= W; j++) {
            prefixSum[i][j] = grid[i-1][j-1]
                             + prefixSum[i-1][j]
                             + prefixSum[i][j-1]
                             - prefixSum[i-1][j-1];
        }
    }
    
    int count = 0; // 初始化计数器
    
    // 遍历所有可能的 KxK 子区域
    for(int i = K; i <= L; i++) {
        for(int j = K; j <= W; j++) {
            // 计算当前 KxK 子区域的总发电量
            long long total = prefixSum[i][j]
                             - prefixSum[i-K][j]
                             - prefixSum[i][j-K]
                             + prefixSum[i-K][j-K];
            // 如果总发电量满足条件，计数器加一
            if(total >= threshold){
                count++;
            }
        }
    }
    
    // 输出最终结果
    cout << count << "\n";
    
    return 0;
}

下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）

本文收录于，华为OD机试真题（Python/JS/C/C++）

在这里插入图片描述

本站资源均来自互联网，仅供研究学习，禁止违法使用和商用，产生法律纠纷本站概不负责！如果侵犯了您的权益请与我们联系！

转载请注明出处：免费源码网-免费的源码资源网站 » 华为OD机试 - 荒地建设电站 - 滑动窗口（Python/JS/C/C++ 2024 E卷 200分）

点赞(0) 打赏

本文分类：文章资讯
本文标签：华为OD机试 - 荒地建设电站 - 滑动窗口（Python/JS/C/C++ 2024 E卷 200分）
浏览次数：9 次浏览
本文链接：https://freeymw.com/article/29382.html

上一篇 > ppt一键生成免费版软件有哪些？如何高效生成论文答辩？
下一篇 > 如何保证Redis与数据库的数据一致性

评论列表共有 0 条评论

暂无评论

华为OD机试 - 荒地建设电站 - 滑动窗口（Python/JS/C/C++ 2024 E卷 200分）

专栏导读

一、题目描述

二、输入描述

三、输出描述

四、测试用例

测试用例1：

1、输入

2、输出

3、说明

测试用例2：

1、输入

2、输出

3、说明

五、解题思路

1、为什么采用滑动窗口？

2、具体步骤：

六、Python算法源码

七、JavaScript算法源码

八、C算法源码

九、C++算法源码

评论列表 共有 0 条评论

发表评论 取消回复

评论列表共有 0 条评论

发表评论取消回复