bzoj千题计划215：bzoj1047: [HAOI2007]理想的正方形

http://www.lydsy.com/JudgeOnline/problem.php?id=1047

先用单调队列求出每横着n个最大值

再在里面用单调队列求出每竖着n个的最大值

这样一个位置就代表了一个n*n矩阵的最大值

同理求出最小值

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

#define N 1001

int num[N][N];

int mx1[N][N],mx2[N][N];

int mi1[N][N],mi2[N][N];

int q[N],pos[N],h,t;

void read(int &x)

{

    x=; int f=; char c=getchar();

    while(!isdigit(c)) { if(c=='-') f=-; c=getchar();  }

    while(isdigit(c)) { x=x*+c-''; c=getchar(); }

    x*=f;

}

int main()

{

    #ifndef ONLINE_JUDGE

        freopen("data.in","r",stdin);

        freopen("xxy.out","w",stdout);

    #endif

    int a,b,n;

    read(a); read(b); read(n);

    for(int i=;i<=a;++i)

        for(int j=;j<=b;++j)

            read(num[i][j]);

    for(int i=;i<=a;++i)

    {

        h=t=;

        for(int j=;j<=b;++j)

        {

            while(h<t && j-pos[h]+>n) h++;

            while(h<t && num[i][j]>q[t-]) t--;

            q[t]=num[i][j];

            pos[t++]=j;

            if(j>=n) mx1[i][j]=q[h];

        }

    }

    for(int j=n;j<=b;++j)

    {

        h=t=;

        for(int i=;i<=a;++i)

        {

            while(h<t && i-pos[h]+>n) h++;

            while(h<t && mx1[i][j]>q[t-]) t--;

            q[t]=mx1[i][j];

            pos[t++]=i;

            if(i>=n) mx2[i][j]=q[h];

        }

    }

    for(int i=;i<=a;++i)

    {

        h=t=;

        for(int j=;j<=b;++j)

        {

            while(h<t && j-pos[h]+>n) h++;

            while(h<t && num[i][j]<q[t-]) t--;

            q[t]=num[i][j];

            pos[t++]=j;

            if(j>=n) mi1[i][j]=q[h];

        }

    }

    for(int j=n;j<=b;++j)

    {

        h=t=;

        for(int i=;i<=a;++i)

        {

            while(h<t && i-pos[h]+>n) h++;

            while(h<t && mi1[i][j]<q[t-]) t--;

            q[t]=mi1[i][j];

            pos[t++]=i;

            if(i>=n) mi2[i][j]=q[h];

        }

    }

    int ans=2e9;

    for(int i=n;i<=a;++i)

        for(int j=n;j<=b;++j)

            ans=min(ans,mx2[i][j]-mi2[i][j]);

    printf("%d",ans);

}

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

#define N 1001

int num[N][N];

int mx[N][N];

int mi[N][N];

int q[N],pos[N],h,t;

void read(int &x)

{

    x=; int f=; char c=getchar();

    while(!isdigit(c)) { if(c=='-') f=-; c=getchar();  }

    while(isdigit(c)) { x=x*+c-''; c=getchar(); }

    x*=f;

}

int main()

{

    freopen("data.in","r",stdin);

    freopen("std.out","w",stdout);

    int a,b,n;

    read(a); read(b); read(n);

    for(int i=;i<=a;++i)

        for(int j=;j<=b;++j)

            read(num[i][j]);

    int ans=1e9;

    for(int i=;i+n-<=a;++i)

        for(int j=;j+n-<=b;++j)

        {

            int I=i+n-;

            int J=j+n-;

            int p=1e9,q=-1e9;

            for(int k=i;k<=I;++k)

                for(int l=j;l<=J;++l)

                    p=min(p,num[k][l]),q=max(q,num[k][l]);

            ans=min(ans,q-p);

        }

    printf("%d",ans);

}

force

#include<cmath>

#include<cstdlib>

#include<cstdio>

#include<ctime>

using namespace std;

int main()

{

    freopen("data.in","w",stdout);

    srand(time()+);

    int a=,b=;

    int n=rand()%+;

    printf("%d %d %d\n",a,b,n);

    for(int i=;i<=a;++i)

    {

        for(int j=;j<=b;++j) printf("%d ",rand());

        printf("\n");

    }

}

maker

1047: [HAOI2007]理想的正方形

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 3791 Solved: 2095
[Submit][Status][Discuss]

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

秒客网