首页 > 代码库 > bzoj1047: [HAOI2007]理想的正方形

bzoj1047: [HAOI2007]理想的正方形

2024-10-20 17:00:39   209人阅读

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

　　仅一个整数，为a*b矩阵中所有“n*n正方形区域中的最大整数和最小整数的差值”的最小值。

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
两层单调队列
连i,j都打错居然过了三个点。。。QwQ
 1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 using namespace std; 5  6 inline int read(){ 7     char ch; 8     int re=0; 9     bool flag=0;10     while((ch=getchar())!=‘-‘&&(ch<‘0‘||ch>‘9‘));11     ch==‘-‘?flag=1:re=ch-‘0‘;12     while((ch=getchar())>=‘0‘&&ch<=‘9‘)  re=re*10+ch-‘0‘;13     return flag?-re:re;14 }15 16 const int maxn=1001;17 18 int n,m,d,l,r,ans=0x3f3f3f3f;19 int a[maxn][maxn],site[maxn],val[maxn];20 int min_site[maxn][maxn],max_site[maxn][maxn],t1[maxn],t2[maxn];21 22 void init(){23     n=read();  m=read();  d=read();24     for(int i=1;i<=n;i++)25         for(int j=1;j<=m;j++)26             a[i][j]=read();27 }28 29 void solve(){30     for(int i=1;i<=n;i++){31         l=1;  r=1;32         for(int j=1;j<=m;j++){33             while(l<r&&val[r-1]<=a[i][j])  r--;34             val[r]=a[i][j];  site[r]=j;  r++;35             if(site[l]==j-d)  l++;36             if(j>=d)  max_site[i][j]=val[l];37         }38         l=1;  r=1;39         for(int j=1;j<=m;j++){40             while(l<r&&val[r-1]>=a[i][j])  r--;41             val[r]=a[i][j];  site[r]=j;  r++;42             if(site[l]==j-d)  l++;43             if(j>=d)  min_site[i][j]=val[l];44         }45     }46     for(int i=d;i<=m;i++){47         l=1;  r=1;48         for(int j=1;j<=n;j++){49             while(l<r&&val[r-1]>=min_site[j][i])  r--;50             val[r]=min_site[j][i];  site[r]=j;  r++;51             if(site[l]==j-d)  l++;52             if(j>=d)  t1[j]=val[l];53         }54         l=1;  r=1;55         for(int j=1;j<=n;j++){56             while(l<r&&val[r-1]<=max_site[j][i])  r--;57             val[r]=max_site[j][i];  site[r]=j;  r++;58             if(site[l]==j-d)  l++;59             if(j>=d)  t2[j]=val[l];60         }61         for(int j=d;j<=n;j++)  ans=min(ans,t2[j]-t1[j]);62     }63     printf("%d\n",ans);64 }65 66 int main(){67     //freopen("temp.in","r",stdin);68     init();69     solve();70     return 0;71 }

 

bzoj1047: [HAOI2007]理想的正方形


联系
我们