思路
这一题还是有些复杂的,先说一下大致思路:
- 任选两列,把这两列间的元素相加成一列,即一维数组,实际宽度为 j - i + 1
- 遍历一维数组,找到和大于等于 K 的最短连续子序列,长度为 len
- 那么上面对应的子矩阵的面积为 (j - i + 1) * len
- 重复上述过程找到最小值
我们先来看一道这样的题目,求一维数组里,大于等于给定任意正整数 K 的最短连续子序列的长度。我们可以用两个指针初始化指向头部,然后 end 指针逐渐后移,直到符合条件的子序列出现,记录当前的长度,然后前指针后移,直到 sum < K,之后 end 指针继续后移。一遍下来就可以完成目标。
我们再来看这道题,我们看看能不能将二维数组降维,选出任意两列,将这两列之间每行的元素相加,得到一个一维数组,对这个一维数组运用上面的最短连续子序列和的算法。时间为O(n),选择任意两列的时候,两个for循环,时间为O(n*2)
#include <iostream> #include <cstring> using namespace std; int matrix[110][110]; int num[110]; int N, M, K; // 将第 i 列和第 j 列之间的元素相加得到一维数组 void merge(int i,int j){ for(int p = 0; p < N; p ++){ for(int k = i; k <= j; k ++){ num[p] += matrix[p][k]; //合并成一维数组 } } } // 在一维数组中寻找大于等于 K 的最短连续子序列 int findShortest(){ int start = 0 ,end = 0; int sum = 0, ans = N + 1; bool flag = false; while(end < N){ if(sum < K){ sum += num[end]; } while(sum >= K){ flag = true; ans = min(ans, end-start+1); sum -= num[start++]; } end ++; } if(flag) return ans; else return N*M; //全部加起来值都没超过K } int main(){ while(cin >> N >> M >> K){ int sum = 0; // 初始化 for(int i = 0; i < N; i ++){ for(int j = 0; j < M; j ++){ cin >> matrix[i][j]; sum += matrix[i][j]; } } if(sum < K) cout << -1 << endl; else{ int minArea = N * M; for(int i = 0; i < M; i ++){ for(int j = i; j < M; j ++){ // 选择任意两列进行合并 memset(num, 0, sizeof(num)); merge(i, j); // 在一维数组中进行查找 int temp = findShortest(); temp = (j - i + 1) * temp; minArea = min(minArea, temp); } } cout << minArea << endl; } } return 0; }