题目描述
一种新型的激光炸弹,可以摧毁一个边长为R
的正方形内的所有的目标。现在地图上有n(n≤10000
)个目标,用整数Xi
,Yi
(其值在[0,5000]
)表示目标在地图上的位置,每个目标都有一个价值。激光炸弹的投放是通过卫星定位的,但其有一个缺点,就是其爆破范围,即那个边长为R
的正方形的边必须和x
,y
轴平行。若目标位于爆破正方形的边上,该目标将不会被摧毁。
暴力思路
- 枚举每一个边长为
R
的正方形 (两重循环)- 得到该矩形的和(两重循环)
四重循环(超时)
改进思路
- 使用二维前缀和(递推)
- 枚举矩阵右下角
- 前缀和求和公式 -> O(1)
AC代码
#include<bits/stdc++.h>
#define N 1010
using namespace std;
int a[N][N];
int s[N][N];
// 内存较紧张时,可以只声明前缀和数组
int main() {
int n, m, c;
scanf("%d%d%d", &n, &m, &c);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%d", &a[i][j]);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
}
}
int sum = 0;
int Max = INT_MIN;
int X, Y;
for (int i = c; i <= n; i++) {
for (int j = c; j <= m; j++) {
sum = s[i][j] - s[i - c][j] - s[i][j - c] + s[i - c][j - c];
if (Max < sum) {
Max = sum;
X = i, Y = j;
}
}
}
printf("%d %d", X - c + 1, Y - c + 1);
return 0;
}