2024华为OD机试（C卷+D卷+E卷）最新题库【超值优惠】Java/Python/C++合集
题目描述
祖国西北部有一片大片荒地，其中零星的分布着一些湖泊，保护区，矿区;整体上常年光照良好，但是也有一些地区光照不太好。某电力公司希望在这里建设多个光伏电站，生产清洁能源，对每平方公里的土地进行了发电评估，其中不能建设的区域发电量为0kw，可以发电的区域根据光照，地形等给出了每平方公里年发电量x千瓦。我们希望能够找到其中集中的矩形区域建设电站，能够获得良好的收益。
输入描述
第一行输入为调研的地区长，宽，以及准备建设的电站【长宽相等，为正方形】的边长，最低要求的发电量
之后每行为调研区域每平方公里的发电量
例如，输入为:
2 5 2 6
1 3 4 5 8
2 3 6 7 1
表示调研的区域大小为长2宽5的矩形，我们要建设的电站的边长为2，建设电站最低发电量为6
输出描述
输出为这样的区域有多少个
上述输入长宽为2的正方形满足发电量大于等于6的区域有4个。
则输出为:
4
示例1
输入：
2 5 2 6
1 3 4 5 8
2 3 6 7 1
输出：
4
说明：
输入长为2，宽为5的场地，建设的场地为正方形场地，边长为2，要求场地的发电量大于等于6
示例2
输入：
2 5 1 6
1 3 4 5 8
2 3 6 7 1
输出：
3
说明：
输入长为2，宽为5的场地，建设的场地为正方形场地，边长为1，要求场地的发电量大于等于6
示例3
输入：
2 5 1 0
1 3 4 5 8
2 3 6 7 1
输出：
10
说明：
输入长为2，宽为5的场地，建设的场地为正方形场地，边长为1，要求场地的发电量大于等于0即可
题解
题目分析
这道题目要求我们在给定的调研区域中找到可以满足条件的矩形区域，这些矩形区域的边长固定，且需要发电量大于等于给定的阈值。题目提到我们可以利用前缀和来加速计算，因此我们可以通过构建二维前缀和来快速得到每个正方形区域的发电量和，从而判断是否满足要求。
代码解析
代码中使用了二维前缀和的思想，步骤具体如下：
- 读取输入：
- 从输入中首先读取矩形的长、宽，正方形电站的边长
B和最低发电量要求MIN。接着读取每个点的发电量，并将其存入二维数组a中。
构建二维前缀和数组：
通过双层循环来构建二维前缀和数组
sum，并利用公式：sum[i+1][j+1]=sum[i+1][j]+sum[i][j+1]−sum[i][j]+a[i][j]这样就能快速计算出任意子矩形的和。
遍历所有可能的左上角：
- 通过两层循环遍历矩形区域的每个可能的左上角
(r1, c1)，然后根据当前的正方形边长B计算出右下角(r2, c2)，判断该区域是否满足发电量要求。
计数结果并输出：
- 如果某个区域的发电量和大于等于
MIN，就将计数器result加 1。最后输出满足条件的区域个数。复杂度分析
时间复杂度：构建二维前缀和的时间复杂度是 O(Length * Width)，然后计算每个正方形区域和的时间复杂度是 O(Length * Width)。因此，整个算法的时间复杂度是 O(Length * Width)，可以处理较大的数据规模。
空间复杂度：我们额外使用了一个大小为
(Length + 1) * (Width + 1)的二维前缀和数组，因此空间复杂度是 O(Length * Width)。总结
本题通过二维前缀和来快速计算任意矩形区域的发电量和，并根据发电量和的大小来判断是否满足条件。使用前缀和大大优化了子矩形的求和效率，使得时间复杂度从 O(n^4) 降到了 O(n^2)，可以处理较大的数据规模。
Java
import java.util.Scanner;
/**
* @author code5bug
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 地区长，宽
int Length = sc.nextInt(), Width = sc.nextInt();
// 准备建设的电站的边长， 最低要求的发电量
int B = sc.nextInt(), MIN = sc.nextInt();
int[][] a = new int[Length][Width];
// 二维前缀和数组
int[][] sum = new int[Length + 1][Width + 1];
for (int i = 0; i < Length; i++) {
for (int j = 0; j < Width; j++) {
a[i][j] = sc.nextInt();
sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + a[i][j];
}
}
int result = 0;
for (int r1 = 0; r1 < Length; r1++) {
for (int c1 = 0; c1 < Width; c1++) {
int r2 = r1 + B, c2 = c1 + B;
if (r2 > Length || c2 > Width) continue;
if (sum[r2][c2] - sum[r2][c1] - sum[r1][c2] + sum[r1][c1] >= MIN) result++;
}
}
System.out.println(result);
}
}
Python
# 输入
Length, Width, B, MIN = map(int, input().split())
# 初始化二维数组
a = [list(map(int, input().split())) for _ in range(Length)]
# 二维前缀和数组
sum = [[0] * (Width + 1) for _ in range(Length + 1)]
# 计算前缀和
for i in range(Length):
for j in range(Width):
sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + a[i][j]
result = 0
# 遍历每个左上角位置，计算是否符合条件
for r1 in range(Length):
for c1 in range(Width):
r2 = r1 + B
c2 = c1 + B
if r2 > Length or c2 > Width:
continue
if sum[r2][c2] - sum[r2][c1] - sum[r1][c2] + sum[r1][c1] >= MIN:
result += 1
# 输出结果
print(result)
C++
#include <iostream>
#include <vector>
using namespace std;
int main() {
// 输入地区的长和宽
int Length, Width;
// 输入电站的边长和最低要求的发电量
int B, MIN;
cin >> Length >> Width >> B >> MIN;
// 初始化二维数组
vector<vector<int>> a(Length, vector<int>(Width));
// 二维前缀和数组
vector<vector<int>> sum(Length + 1, vector<int>(Width + 1, 0));
// 输入二维数组并计算前缀和
for (int i = 0; i < Length; i++) {
for (int j = 0; j < Width; j++) {
cin >> a[i][j];
sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + a[i][j];
}
}
int result = 0;
// 遍历每个左上角位置，计算是否符合条件
for (int r1 = 0; r1 < Length; r1++) {
for (int c1 = 0; c1 < Width; c1++) {
int r2 = r1 + B, c2 = c1 + B;
if (r2 > Length || c2 > Width) continue; // 边界检查
// 计算子矩阵的和并检查是否大于等于最低要求
if (sum[r2][c2] - sum[r2][c1] - sum[r1][c2] + sum[r1][c1] >= MIN) {
result++;
}
}
}
// 输出结果
cout << result << endl;
return 0;
}
相关练习题
| 题号 | 题目 | 难易 |
|---|---|---|
| LeetCode 304 | 304. 二维区域和检索 - 矩阵不可变 | 中等 |
整理题解不易， 如果有帮助到您，请给点个赞 ❤️ 和收藏 ⭐，让更多的人看到。🙏🙏🙏
