首页 > 代码库 > BZOJ 1047 HAOI 2007 理想的正方形 单调队列
BZOJ 1047 HAOI 2007 理想的正方形 单调队列
题目大意:给出一个矩阵,求出一个k*k的子矩阵,使得这个矩阵中最大值和最小值的差最小,输出这个差值。
思路:利用单调队列维护每一行的数字,求出一个数字前面k个数字中的最大值和最小值,然后在列上暴力求出真个矩阵的最大值和最小值,总时间复杂度O(M*M+M*M*K)。
CODE:
#include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 1010 #define INF 0x3f3f3f3f using namespace std; struct Status{ int num,pos; Status(int _,int __):num(_),pos(__) {} }; int m,n,k; int src[MAX][MAX]; int _max[MAX][MAX],_min[MAX][MAX]; inline void Calc(int line) { deque<Status> __min,__max; for(int i = 1; i <= n; ++i) { while(!__min.empty() && i - __min.front().pos >= k) __min.pop_front(); while(!__max.empty() && i - __max.front().pos >= k) __max.pop_front(); Status now(src[line][i],i); while(!__min.empty() && now.num <= __min.back().num) __min.pop_back(); while(!__max.empty() && now.num >= __max.back().num) __max.pop_back(); __min.push_back(now); __max.push_back(now); _min[line][i] = __min.front().num; _max[line][i] = __max.front().num; } } int main() { cin >> m >> n >> k; for(int i = 1; i <= m; ++i) for(int j = 1; j <= n; ++j) scanf("%d",&src[i][j]); for(int i = 1; i <= m; ++i) Calc(i); int ans = INF; for(int i = 1; i <= m - k + 1; ++i) for(int j = k; j <= n; ++j) { int __min = INF,__max = -INF; for(int l = 0; l < k; ++l) { __min = min(__min,_min[i + l][j]); __max = max(__max,_max[i + l][j]); } ans = min(ans,__max - __min); } cout << ans << endl; return 0; }
BZOJ 1047 HAOI 2007 理想的正方形 单调队列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。