使用前缀和暴力枚举
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110, INF = 0x3f3f3f3f;
int g[N][N];
int n, m, s;
int main() {
cin >> n >> m >> s;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++) {
cin >> g[i][j];
g[i][j] += g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1]; //构造前缀和矩阵
}
int cnt = INF;
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
for (int k = i; k <= n; k ++) {
for (int l = j; l <= m; l ++) {
//计算左上角为[i,j],右下角为[k,l]的矩阵中所有元素的和
int sum = g[k][l] - g[i - 1][l] - g[k][j - 1] + g[i - 1][j - 1];
if (sum >= s) {
//计算矩阵中的最小元素个数
cnt = min(cnt, (k - i + 1) * (l - j + 1));
}
}
}
}
}
if (cnt == INF) cnt = -1;
cout << cnt << endl;
return 0;
}
双指针优化版
x行和y行已经确定,而j列和i列的位置关系可以优化,设置j是最右侧并且元素和大于等于k的位置,i向前进的时候,j只能向前进,不可能再后退,这两个指针一共走2n次,复杂度就降到了O(n)级别。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110, INF = 100010;
int g[N][N];
int n, m, k;
int main() {
cin >> n >> m >> k;
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
cin >> g[i][j];
g[i][j] += g[i - 1][j]; //求出每列的前缀和,与行无关,每一列至上到下,用作到后面的
} //双指针的时候整列平移
}
int res = INF;
for (int x = 1; x <= n; x ++) {
for (int y = x; y <= n; y ++) {
for (int i = 1, j = 1, sum = 0; i <= m; i ++) {
sum += g[y][i] - g[x - 1][i];
while (sum - g[y][j] + g[x - 1][j] >= k) {
sum -= g[y][j] - g[x - 1][j];
j ++;
}
if (sum >= k) res = min(res, (y - x + 1) * (i - j + 1));
}
}
}
if (res == INF) res = -1;
cout << res << endl;
return 0;
}