BZOJ 1047 HAOI2007 理想的正方形 单调队列
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
题目大意：给定一个a*b的矩阵，求一个n*n的子矩阵，使矩阵中的最大值与最小值之差最小
对于每行维护一个单调递减的队列，再弄一个竖着的队列，维护n个格子之内的最大值即可
两遍统计出最大值和最小值 然后得到ans即可
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 1010
using namespace std;
struct abcd{
pair<int,int>queue[M];
int r,h;
void Insert(int x,int pos);
int Get_Num();
}qs[M],q;
int m,n,k,ans=0x3f3f3f3f;
int map[M][M],max_num[M][M],min_num[M][M];
void abcd :: Insert(int x,int pos)
{
while(r!=h&&queue[r].first<=x)
--r;
queue[++r]=make_pair(x,pos);
while(queue[h+1].second<=pos-k)
++h;
}
int abcd :: Get_Num()
{
return queue[h+1].first;
}
int main()
{
int i,j;
cin>>m>>n>>k;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
scanf("%d",&map[i][j]);
for(i=1;i<=m;i++)
for(j=1;j<k;j++)
qs[i].Insert(map[i][j],j);
for(j=k;j<=n;j++)
{
for(i=1;i<=m;i++)
qs[i].Insert(map[i][j],j);
memset(&q,0,sizeof q);
for(i=1;i<k;i++)
q.Insert(qs[i].Get_Num(),i);
for(i=k;i<=m;i++)
q.Insert(qs[i].Get_Num(),i),max_num[i][j]=q.Get_Num();
}
memset(qs,0,sizeof qs);
for(i=1;i<=m;i++)
for(j=1;j<k;j++)
qs[i].Insert(-map[i][j],j);
for(j=k;j<=n;j++)
{
for(i=1;i<=m;i++)
qs[i].Insert(-map[i][j],j);
memset(&q,0,sizeof q);
for(i=1;i<k;i++)
q.Insert(qs[i].Get_Num(),i);
for(i=k;i<=m;i++)
q.Insert(qs[i].Get_Num(),i),min_num[i][j]=-q.Get_Num();
}
for(i=k;i<=m;i++)
for(j=k;j<=n;j++)
ans=min(ans,max_num[i][j]-min_num[i][j]);
cout<<ans<<endl;
}| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |