- 题目描述：
-
一个N*M的矩阵，找出这个矩阵中所有元素的和不小于K的面积最小的子矩阵（矩阵中元素个数为矩阵面积）
- 输入：
-
每个案例第一行三个正整数N,M<=100，表示矩阵大小，和一个整数K
接下来N行，每行M个数，表示矩阵每个元素的值
- 输出：
-
输出最小面积的值。如果出现任意矩阵的和都小于K，直接输出-1。
- 样例输入：
-
4 4 101 2 3 45 6 7 89 10 11 1213 14 15 16
- 样例输出：
-
1 这道题的题意读了半天才读懂，它是要求输出满足条件的最小的矩阵面积。 解决这类问题的重要办法就是降维，将二维降为一维。选取两列，将两列间元素相加，化为一维，再选取最小的大于k的最小连续长度 第一版代码是这样：
1 #include
2 #include 3 #include 4 #include 5 #define MAX 102 6 7 int matrix[MAX][MAX]; 8 int tr[MAX]; 9 10 int main(int argc, char const *argv[])11 {12 int n, m, k;13 //freopen("input.txt","r",stdin);14 while(scanf("%d %d %d",&n, &m, &k) != EOF) {15 for(int i = 0; i < n; i++) {16 for(int j = 0; j < m; j++) {17 scanf("%d",&matrix[i][j]);18 }19 }20 21 int ans = n*m + 1;22 for(int i = 0; i < m; i++) {23 for(int j = i; j < m; j++) {24 //from i to j25 memset(tr,0,sizeof(tr));26 int ansij = -1;27 28 int base = j - i + 1;29 for(int h = 0; h < n; h++) {30 for(int q = i; q <= j; q++) {31 tr[h] = tr[h] + matrix[h][q];32 }33 }34 /*for(int h = 0; h < n; h++) {35 printf("%d ",tr[h]);36 }37 puts("");*/38 for(int len = 1; len <= n; len++) {39 for(int u = 0; u < n; u++) {40 int v = u + len -1;41 if(v >= n) {42 break;43 }44 int sum = 0;45 for(int w = u; w <= v; w++) {46 sum = sum + tr[w];47 }48 if(sum >= k) {49 ansij = len;50 break;51 }52 }53 if(ansij != -1) {54 break;55 }56 }57 if(ansij != -1 && ansij *base < ans) {58 ans = ansij*base;59 }60 }61 }62 if(ans < n*m+1) {63 printf("%d\n", ans);64 }65 else {66 puts("-1");67 }68 69 }70 return 0;71 } 时间为150ms
后来发现31行的累加很费时间，后来发现这个累加完全可以不用每回从头开始加，上一次的结果可以作为下一次的开始，代码修改为
1 #include
2 #include 3 #include 4 #include 5 #define MAX 102 6 7 int matrix[MAX][MAX]; 8 int tr[MAX]; 9 10 int main(int argc, char const *argv[])11 {12 int n, m, k;13 //freopen("input.txt","r",stdin);14 while(scanf("%d %d %d",&n, &m, &k) != EOF) {15 for(int i = 0; i < n; i++) {16 for(int j = 0; j < m; j++) {17 scanf("%d",&matrix[i][j]);18 }19 }20 21 int ans = n*m + 1;22 for(int i = 0; i < m; i++) {23 memset(tr,0,sizeof(tr));24 for(int j = i; j < m; j++) {25 //from i to j26 int ansij = -1;27 28 int base = j - i + 1;29 for(int h = 0; h < n; h++) {30 tr[h] = tr[h] + matrix[h][j]; 31 32 }33 /*for(int h = 0; h < n; h++) {34 printf("%d ",tr[h]);35 }36 puts("");*/37 for(int len = 1; len <= n; len++) {38 for(int u = 0; u < n; u++) {39 int v = u + len -1;40 if(v >= n) {41 break;42 }43 int sum = 0;44 for(int w = u; w <= v; w++) {45 sum = sum + tr[w];46 }47 if(sum >= k) {48 ansij = len;49 break;50 }51 }52 if(ansij != -1) {53 break;54 }55 }56 if(ansij != -1 && ansij *base < ans) {57 ans = ansij*base;58 }59 }60 }61 if(ans < n*m+1) {62 printf("%d\n", ans);63 }64 else {65 puts("-1");66 }67 68 }69 return 0;70 } 时间为120ms
发现在45行仍有累加，修改为如下：
1 #include
2 #include 3 #include 4 #include 5 #define MAX 102 6 7 int matrix[MAX][MAX]; 8 int tr[MAX]; 9 int dis[MAX][MAX];10 11 int cal(int u, int v) {12 if(dis[u][v] != 0) {13 return dis[u][v]; 14 }15 if(v == u) {16 dis[u][v] = tr[u];17 return dis[u][v];18 }19 else {20 dis[u][v] = dis[u][v-1] + dis[v][v];21 return dis[u][v-1] + dis[v][v];22 }23 }24 25 int main(int argc, char const *argv[])26 {27 int n, m, k;28 //freopen("input.txt","r",stdin);29 while(scanf("%d %d %d",&n, &m, &k) != EOF) {30 for(int i = 0; i < n; i++) {31 for(int j = 0; j < m; j++) {32 scanf("%d",&matrix[i][j]);33 }34 }35 36 int ans = n*m + 1;37 for(int i = 0; i < m; i++) {38 memset(tr,0,sizeof(tr));39 for(int j = i; j < m; j++) {40 //from i to j41 int ansij = -1;42 43 int base = j - i + 1;44 for(int h = 0; h < n; h++) {45 tr[h] = tr[h] + matrix[h][j]; 46 47 }48 /*for(int h = 0; h < n; h++) {49 printf("%d ",tr[h]);50 }51 puts("");*/52 memset(dis,0,sizeof(dis));53 54 for(int len = 1; len <= n; len++) {55 for(int u = 0; u < n; u++) {56 int v = u + len -1;57 if(v >= n) {58 break;59 }60 int sum = cal(u,v);61 if(sum >= k) {62 ansij = len;63 break;64 }65 }66 if(ansij != -1) {67 break;68 }69 }70 if(ansij != -1 && ansij *base < ans) {71 ans = ansij*base;72 }73 }74 }75 if(ans < n*m+1) {76 printf("%d\n", ans);77 }78 else {79 puts("-1");80 }81 82 }83 return 0;84 } 时间为60ms
后来参考别人的代码，可以利用尺取法解决这个问题
1 #include
2 #include 3 #include 4 #include 5 #define MAX 102 6 7 int matrix[MAX][MAX]; 8 int tr[MAX]; 9 10 int merge(int n, int goal) {11 int ans = -1;12 int start = 0, end = 0, sum = 0;13 while (end < n) {14 if (sum < goal)15 sum += tr[end];16 while (sum >= goal) {17 int len = end - start + 1;18 if (ans == -1) ans = len;19 else if (len < ans) ans = len;20 sum -= tr[start++];21 }22 ++end;23 }24 return ans;25 }26 27 int main(int argc, char const *argv[])28 {29 int n, m, k;30 //freopen("input.txt","r",stdin);31 while(scanf("%d %d %d",&n, &m, &k) != EOF) {32 for(int i = 0; i < n; i++) {33 for(int j = 0; j < m; j++) {34 scanf("%d",&matrix[i][j]);35 }36 }37 38 int ans = n*m + 1;39 for(int i = 0; i < m; i++) {40 memset(tr,0,sizeof(tr));41 for(int j = i; j < m; j++) {42 //from i to j43 int ansij = -1;44 45 int base = j - i + 1;46 for(int h = 0; h < n; h++) {47 tr[h] = tr[h] + matrix[h][j]; 48 49 }50 /*for(int h = 0; h < n; h++) {51 printf("%d ",tr[h]);52 }53 puts("");*/54 ansij = merge(n, k);55 if(ansij != -1 && ansij *base < ans) {56 ans = ansij*base;57 }58 }59 }60 if(ans < n*m+1) {61 printf("%d\n", ans);62 }63 else {64 puts("-1");65 }66 67 }68 return 0;69 } 时间居然缩短到了10ms