首页 > 代码库 > SPOJ MINSUB - Largest Submatrix（二分+单调栈）
SPOJ MINSUB - Largest Submatrix（二分+单调栈）
http://www.spoj.com/problems/MINSUB/en/
题意：给出一个n*m的矩阵M，和一个面积k，要使得M的子矩阵M‘的最小元素最大并且面积大于等于k，问子矩阵M‘的最小元素最大能是多少，并且求出最大的面积。
思路：二分一个最小元素x，转化为判断矩阵M里面是否存在一个子矩阵使得这个子矩阵的面积大于等于k并且所有元素都大于x。
用另一个矩阵，1表示该位置的元素大于等于x，0表示元素小于x。
转化为判断是否存在一个子矩阵元素为1的面积大于等于k。
这样可以用到早上学习的单调栈，去维护最大的子矩阵面积。
像这样，求出最大的矩阵面积。
如果矩阵面积大于等于k，那么就去找是否有更大的x去满足题意。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define N 1010 4 struct node { 5 int pre, suf, val; 6 } p[N]; 7 int mat[N][N], mp[N][N], h[N][N], n, m, k, square; 8 9 bool check(int x) {10 memset(mp, 0, sizeof(mp));11 memset(h, 0, sizeof(h));12 for(int i = 1; i <= n; i++)13 for(int j = 1; j <= m; j++) if(mat[i][j] >= x) mp[i][j] = 1;14 square = 0;15 for(int i = 1; i <= n; i++) {16 stack<node> sta;17 for(int j = 1; j <= m; j++) {18 if(mp[i][j]) h[i][j] = h[i-1][j] + 1;19 p[j] = (node) {1, 1, h[i][j]};20 }21 sta.push(p[1]);22 for(int j = 2; j <= m; j++) {23 while(!sta.empty() && sta.top().val > p[j].val) {24 node top = sta.top(); sta.pop();25 if(!sta.empty()) sta.top().suf += top.suf;26 p[j].pre += top.pre;27 square = max(square, (top.suf + top.pre - 1) * top.val);28 }29 sta.push(p[j]);30 }31 while(!sta.empty()) {32 node top = sta.top(); sta.pop();33 if(!sta.empty()) sta.top().suf += top.suf;34 square = max(square, (top.suf + top.pre - 1) * top.val);35 }36 }37 if(square >= k) return true;38 return false;39 }40 41 void solve() {42 int t;43 scanf("%d", &t);44 while(t--) {45 scanf("%d%d%d", &n, &m, &k);46 int r = 0, l = 1000000000, ans;47 for(int i = 1; i <= n; i++) {48 for(int j = 1; j <= m; j++) {49 scanf("%lld", &mat[i][j]);50 if(mat[i][j] < l) l = mat[i][j];51 if(mat[i][j] > r) r = mat[i][j];52 }53 }54 ans = l;55 while(l <= r) {56 int mid = (l + r) >> 1;57 if(check(mid)) l = mid + 1, ans = mid;58 else r = mid - 1;59 }60 check(ans);61 printf("%d %d\n", ans, square);62 }63 }64 65 int main() {66 solve();67 return 0;68 }
SPOJ MINSUB - Largest Submatrix（二分+单调栈）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。