「HAOI2007」理想的正方形

Description

有一个a*b的整数组成的矩阵,现请你从中找出一个n*n的正方形区域,使得该区域所有数中的最大值和最小值的差最小.

Input

第一行为3个整数,分别表示a,b,n的值第二行至第a+1行每行为b个非负整数,表示矩阵中相应位置上的数.每行相邻两数之间用一空格分隔.
100%的数据2<=a,b<=1000,n<=a,n<=b,n<=1000

Output

仅一个整数,为ab矩阵中所有”nn正方形区域中的最大整数和最小整数的差值”的最小值.

Sample Input

5 4 2

1 2 5 6

0 17 16 0

16 17 2 1

2 10 2 1

1 2 2 2

Sample Output

1

Solution

维护单调队列,maxx[i][j]表示第i行以j为结尾的长度为min(j,len)的序列最大值;minn[i][j]表示第i行以j为结尾的长度为min(j,len)的序列最小值.
可以相当于使之缩成一个点,因此有ansx[i][j]表示以(i,j)为右下方端点,边长为min(j,len)的正方形的最大值;ansn[i][j]表示以(i,j)为右下方端点,边长为min(j,len)的正方形的最小值.
最后n²枚举右下方端点更新答案即可.

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<queue>
#include<vector>
#include<algorithm>
#include<cmath>
#include<stack>
using namespace std;
#define R register
#define ll long long
#define fo(i,a,b) for(R int (i)=(a);(i)<=(b);++(i))
struct node{int id,data;};
int n,m,len,a[1001][1001],maxx[1001][1001],minn[1001][1001];
int ansx[1001][1001],ansn[1001][1001],anss=1e9,l,r;
node q[10001];
node nod(int idd,int da){return node{idd,da};}
int main()
{
scanf("%d%d%d",&n,&m,&len);
fo(i,1,n)
fo(j,1,m)
scanf("%d",&a[i][j]);
fo(i,1,n)
{
l=1,r=0;
fo(j,1,m)
{
R node now=nod(j,a[i][j]);
while(now.id-q[l].id+1>len)l++;
while(q[r].data<=now.data&&l<=r)r--;
q[++r]=now;
maxx[i][j]=q[l].data;
}
}
fo(i,1,n)
{
l=1,r=0;
fo(j,1,m)
{
R node now=nod(j,a[i][j]);
while(now.id-q[l].id+1>len)l++;
while(q[r].data>=now.data&&l<=r)r--;
q[++r]=now;
minn[i][j]=q[l].data;
}
}
fo(j,1,m)
{
l=1,r=0;
fo(i,1,n)
{
R node now=nod(i,maxx[i][j]);
while(now.id-q[l].id+1>len)l++;
while(q[r].data<=now.data&&l<=r)r--;
q[++r]=now;
ansx[i][j]=q[l].data;
}
}
fo(j,1,m)
{
l=1,r=0;
fo(i,1,n)
{
R node now=nod(i,minn[i][j]);
while(now.id-q[l].id+1>len)l++;
while(q[r].data>=now.data&&l<=r)r--;
q[++r]=now;
ansn[i][j]=q[l].data;
}
}
fo(i,len,n)
fo(j,len,m)
anss=min(anss,ansx[i][j]-ansn[i][j]);
cout<<anss;
return 0;
}

显示 Gitment 评论