P2216 [HAOI2007] 理想的正方形
时间限制: 1.00s 内存限制: 128.00MB
复制 Markdown
中文
退出 IDE 模式
题目描述
有一个 a×b 的整数组成的矩阵，现请你从中找出一个 n×n 的正方形区域，使得该区域所有数中的最大值和最小值的差最小。
输入格式
第一行为 3 个整数，分别表示 a,b,n 的值。
第二行至第 a+1 行每行为 b 个非负整数，表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。
输出格式
仅一个整数，为 a×b 矩阵中所有“ n×n 正方形区域中的最大整数和最小整数的差值”的最小值。
输入输出样例
输入 #1复制运行
5 4 2 1 2 5 6 0 17 16 0 16 17 2 1 2 10 2 1 1 2 2 2
输出 #1复制运行
1
说明/提示
矩阵中的所有数都不超过 1,000,000,000。
20% 的数据 2≤a,b≤100,n≤a,n≤b,n≤10。
100% 的数据 2≤a,b≤1000,n≤a,n≤b,n≤100。
先进行一维的单调队列然后将一维的结果再次进行单调队列即可
#include <bits/stdc++.h> using namespace std; const int N=1e3+5; int a[N][N]; int cmax[N][N],cmin[N][N]; int q1[N],q2[N]; int n,m,len; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m>>len; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)cin>>a[i][j]; for(int i=1;i<=n;i++){ int l1=1,l2=1,r1=0,r2=0; for(int j=1;j<=m;j++){ while(l1<=r1&&j-q1[l1]>=len)l1++; while(l2<=r2&&j-q2[l2]>=len)l2++; while(l1<=r1&&a[i][j]>=a[i][q1[r1]])r1--; while(l2<=r2&&a[i][j]<=a[i][q2[r2]])r2--; q1[++r1]=j;q2[++r2]=j; cmax[i][j]=a[i][q1[l1]];cmin[i][j]=a[i][q2[l2]]; } } int ans=INT_MAX; for(int j=len;j<=m;j++){ int l1=1,l2=1,r1=0,r2=0; for(int i=1;i<=n;i++){ while(l1<=r1&&i-q1[l1]>=len)l1++; while(l2<=r2&&i-q2[l2]>=len)l2++; while(l1<=r1&&cmax[i][j]>=cmax[q1[r1]][j])r1--; while(l2<=r2&&cmin[i][j]<=cmin[q2[r2]][j])r2--; q1[++r1]=i;q2[++r2]=i; if(i>=len)ans=min(ans,cmax[q1[l1]][j]-cmin[q2[l2]][j]); } } cout<<ans<<'\n'; return 0; }
