这题就是求一个矩阵中的最小面积矩阵，使得其和大于一个给定的K，由于是求最优解，所以很自然的想到了二分查找这个值，但是这题我却在不去顶是否满足二分性质的前提下匆忙的选择了二分查找，最终导致了错误。原因在与当一个面积为一个最优解的时候，面积大于该最优解的子矩阵不一定包含这个最优矩阵，例如一个5*5的矩阵的，如果最优矩阵是一个2*2的矩阵，那么1*5的面积为5的矩阵式不会包含这个2*2的矩阵的，所以......
代码如下：
#include#include #include #include #define MAXN 105using namespace std;int N, M, K, G[MAXN][MAXN], S[MAXN*MAXN], lim;int rec[MAXN*MAXN], idx, sum[MAXN][MAXN];struct Node{ int x, y;}que[MAXN];int front, tail;inline void pre(){ int k; lim = N*M; memset(S, 0, sizeof (S)); idx = -1; // getstatus for (int i = 1; i <= N; ++i) { k = min(M, lim / i); // 选取相对小的值,排除不合法情况 for (int j = 1; j <= k; ++j) { S[i*j] = 1; } } for (int i = 1; i <= lim; ++i) { if (S[i]) { rec[++idx] = i; } } // getsum for (int i = 1; i <= N; ++i) { for (int j = 1; j <= M; ++j) { sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + G[i][j]; } }}bool judge(){ int xx, yy, zz, lx, ly; for (int k = 1; k <= tail; ++k) { lx = N - que[k].x + 1, ly = M - que[k].y + 1; for (int i = 1; i <= lx; ++i) { for (int j = 1; j <= ly; ++j) { xx = i+que[k].x-1, yy = j+que[k].y-1; if (xx <= N && yy <= M) { zz = sum[xx][yy] - sum[i-1][yy] - sum[xx][j-1] + sum[i-1][j-1]; if (zz >= K) return true; } } } } return false;}bool Ac(int x) // 能够保证所有的x都是合法值 { front = tail = 0; for (int i = 1; i <= N; ++i) { if (x % i == 0) { ++tail; que[tail].x = i, que[tail].y = x / i; } } // 处理处当前面积的分解情况 if (judge()) { return true; } return false;}int bsearch(int l, int r){ int mid, ret = -1; while (l <= r) { mid = (l + r) >> 1; if (Ac(rec[mid])) { ret = rec[mid]; r = mid - 1; } else { l = mid + 1; } } return ret;}int force(){ for (int i = 0; i <= idx; ++i) { if (Ac(rec[i])) { return rec[i]; } } return -1;}int main(){ while (scanf("%d %d %d", &N, &M, &K) != EOF) { for (int i = 1; i <= N; ++i) { for (int j = 1; j <= M; ++j) { scanf("%d", &G[i][j]); } } pre(); // printf("%d\n", bsearch(0, idx)); printf("%d\n", force()); } return 0; }