传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1047
先用单调队列横着预处理出每行连续的k个的极值
再竖着做一遍单调队列就行了
Code:
#include<cstdio> #include<iostream> #include<algorithm> #include<cctype> #include<climits> #include<queue> #include<cstdlib> using namespace std; const int maxn=1005; typedef pair<int,int> pii; int n,m,k,ans=INT_MAX; int mp[maxn][maxn]; int Min[maxn][maxn]; int Max[maxn][maxn]; int getint(){ int res=0;char c=getchar(); while(!isdigit(c))c=getchar(); while(isdigit(c))res=res*10+c-'0',c=getchar(); return res; } deque<pii>qmax,qmin; void deb(deque<pii> q){ for(int i=0;i<q.size();i++)printf("%d%c",q[i].first," \n"[i==q.size()-1]); } int main(){ scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)mp[i][j]=getint(); for(int i=1;i<=n;i++){ qmax.clear();qmin.clear(); for(int j=1;j<=m;j++){ while(qmax.size()&&qmax.front().second<j-k+1)qmax.pop_front(); while(qmin.size()&&qmin.front().second<j-k+1)qmin.pop_front(); while(qmax.size()&&qmax.back().first<=mp[i][j])qmax.pop_back(); qmax.push_back(pii(mp[i][j],j)); while(qmin.size()&&qmin.back().first>=mp[i][j])qmin.pop_back(); qmin.push_back(pii(mp[i][j],j)); Min[i][j]=qmin.front().first;Max[i][j]=qmax.front().first; } } for(int j=k;j<=m;j++){ qmax.clear();qmin.clear(); for(int i=1;i<=n;i++){ while(qmax.size()&&qmax.front().second<i-k+1)qmax.pop_front(); while(qmin.size()&&qmin.front().second<i-k+1)qmin.pop_front(); while(qmax.size()&&qmax.back().first<=Max[i][j])qmax.pop_back(); qmax.push_back(pii(Max[i][j],i)); while(qmin.size()&&qmin.back().first>=Min[i][j])qmin.pop_back(); qmin.push_back(pii(Min[i][j],i)); if(i>=k&&j>=k) ans=min(ans,qmax.front().first-qmin.front().first); } }cout<<ans<<endl; return 0; }