題目鏈接：https://www.luogu.org/problem/P2216

題意：求給定n*m的矩形中所有k*k的正方形塊中最大值最小值之差（極差）最小

哇，大神的思路真的很帥

單調(diào)隊(duì)列對(duì)每一行求一個(gè)k項(xiàng)最大最小

用X[i][j]表示第i行小于j-k+1~j的最大值

用X[i][j]表示第i行小于j-k+1~j的最大值

然后處理完行之后，用X，x數(shù)組作為基礎(chǔ)對(duì)每一列求最大最小,用Y,y表示

這樣處理完的Y[i][j]就表示以i，j為右下角的k*k矩形的最大值

這樣處理完的y[i][j]就表示以i，j為右下角的k*k矩形的最小值

給他起個(gè)名字就叫二位單調(diào)隊(duì)列吧QAQ~

此圖是偷的~

代碼如下啦：

//#pragma comment (linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#include<list>
#include<time.h>
#include<bitset>#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define lowbit(x) x&(-x)
#define min4(a, b, c, d) min(min(a,b),min(c,d))
#define min3(x, y, z) min(min(x,y),z)
#define max3(x, y, z) max(max(x,y),z)
#define max4(a, b, c, d) max(max(a,b),max(c,d))
#define pii make_pair
#define pr pair<int,int>
typedef unsigned long long ull;
typedef long long ll;
const int inff = 0x3f3f3f3f;
const long long inFF = 9223372036854775807;
const int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
const int mdir[8][2] = {0, 1, 0, -1, 1, 0, -1, 0, 1, 1, -1, 1, 1, -1, -1, -1};
const double eps = 1e-10;
const double PI = acos(-1.0);
const double E = 2.718281828459;
using namespace std;
const int mod=1e9+7;
const int maxn=1005;
int a[maxn][maxn];
int X[maxn][maxn],x[maxn][maxn],Y[maxn][maxn],y[maxn][maxn];
int Q[maxn],q[maxn];
int main()
{int n,m,k;cin>>n>>m>>k;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);for(int i=1;i<=n;i++){int l=0,r=0,L=0,R=0;Q[0]=0,q[0]=0;for(int j=1;j<=m;j++){while(l<=r&&a[i][j-1]<=a[i][q[r]]) r--;while(L<=R&&a[i][j-1]>=a[i][Q[R]]) R--;q[++r]=j-1,Q[++R]=j-1;while(l<=r&&q[l]<=j-k) l++;while(L<=R&&Q[L]<=j-k) L++;x[i][j]=min(a[i][q[l]],a[i][j]);X[i][j]=max(a[i][Q[L]],a[i][j]);}}for(int i=k;i<=m;i++){int l=0,r=0,L=0,R=0;Q[0]=0,q[0]=0;for(int j=1;j<=n;j++){while(l<=r&&x[j-1][i]<=x[q[r]][i]) r--;while(L<=R&&X[j-1][i]>=X[Q[R]][i]) R--;q[++r]=j-1,Q[++R]=j-1;while(l<=r&&q[l]<=j-k) l++;while(L<=R&&Q[L]<=j-k) L++;y[j][i]=min(x[j][i],x[q[l]][i]);Y[j][i]=max(X[j][i],X[Q[L]][i]);}}int ans=inff;for(int i=k;i<=n;i++)for(int j=k;j<=m;j++)ans=min(ans,Y[i][j]-y[i][j]);cout<<ans<<endl;
}

?

總結(jié)

以上是生活随笔為你收集整理的P2216 理想的正方形 单调队列 （二维）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。