原題鏈接：https://www.luogu.com.cn/problem/P2216
理想的正方形
題目描述
有一個a * b的整陣列成的矩陣，現請你從中找出一個 n * n的正方形區域，使得該區域所有數中的最大值和最小值的差最小，
輸入格式
第一行為3個整數，分別表示a,b,n的值
第二行至第a+1行每行為b個非負整數，表示矩陣中相應位置上的數，每行相鄰兩數之間用一空格分隔，
輸出格式
僅一個整數，為ab矩陣中所有“nn正方形區域中的最大整數和最小整數的差值”的最小值，
輸入輸出樣例
輸入 #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）矩陣中的所有數都不超過1,000,000,000
（2）20%的資料2<=a,b<=100,n<=a,n<=b,n<=10
（3）100%的資料2<=a,b<=1000,n<=a,n<=b,n<=100
題解
二維的滑動視窗，先對每一行做一次橫向的滑動視窗，求出每一行長為 n n n的視窗滑過的最小/大值，再對求出的最小/大值做一次縱向的滑動視窗，這樣求出的就是二維的 n × n n\times n n×n的視窗覆寫的最小/大值，
代碼
看起來多，實際上都是復制粘貼的，一遍過針不戳，
#include<bits/stdc++.h>
using namespace std;
const int M=1e3+5;
int n,a,b,que[M],sqr[M][M],mn[M][M],mx[M][M],mn2[M][M],mx2[M][M],head,tail;
void hori(int x)
{
que[head=tail=1]=1;if(n==1)mn[x][1]=sqr[x][1];
for(int i=2;i<=b;++i)
{
for(;sqr[x][que[tail]]>=sqr[x][i]&&tail>=head;--tail);
que[++tail]=i;
for(;i-que[head]+1>n&&head<=tail;++head);
if(i>=n)mn[x][i]=sqr[x][que[head]];
}
que[head=tail=1]=1;if(n==1)mx[x][1]=sqr[x][1];
for(int i=2;i<=b;++i)
{
for(;sqr[x][que[tail]]<=sqr[x][i]&&tail>=head;--tail);
que[++tail]=i;
for(;i-que[head]+1>n&&head<=tail;++head);
if(i>=n)mx[x][i]=sqr[x][que[head]];
}
}
void verti(int x)
{
que[head=tail=1]=1;if(n==1)mn2[1][x]=mn[1][x];
for(int i=2;i<=a;++i)
{
for(;mn[que[tail]][x]>=mn[i][x]&&tail>=head;--tail);
que[++tail]=i;
for(;i-que[head]+1>n&&head<=tail;++head);
if(i>=n)mn2[i][x]=mn[que[head]][x];
}
que[head=tail=1]=1;if(n==1)mx2[1][x]=mx[1][x];
for(int i=2;i<=a;++i)
{
for(;mx[que[tail]][x]<=mx[i][x]&&tail>=head;--tail);
que[++tail]=i;
for(;i-que[head]+1>n&&head<=tail;++head);
if(i>=n)mx2[i][x]=mx[que[head]][x];
}
}
void in()
{
scanf("%d%d%d",&a,&b,&n);
for(int i=1;i<=a;++i)for(int j=1;j<=b;++j)scanf("%d",&sqr[i][j]);
}
void ac()
{
for(int i=1;i<=a;++i)hori(i);
for(int i=n;i<=b;++i)verti(i);
int ans=INT_MAX;
for(int i=n;i<=a;++i)for(int j=n;j<=b;++j)ans=min(ans,mx2[i][j]-mn2[i][j]);
printf("%d\n",ans);
}
int main()
{
in(),ac();
system("pause");
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/259269.html
標籤：其他
上一篇：微信紅包演算法決議