洛谷 2216 [HAOI2007]理想的正方形

给你一个a×b的矩形，求一个n×n的子矩阵，矩阵里面的最大值和最小值之差最小。

Solution

这个题目许多大佬都是单调队列，但是我不是很会，只好用了比较傻逼的方法：

首先我们预处理出每个点往后走N步的最大值和最小值。复杂度的话是\(O(a*b*n)\)，然后枚举每一个点，往下走N步并比较最大值和最小值，就得到一个N×N的矩阵中的最大值和最小值，然后更新答案即可。

复杂度大概是 1e8，差不多正好卡过去。洛谷评测机是真的快，开氧气优化居然只要200ms

Coding

#include<bits/stdc++.h>

using namespace std;

const int N = 2005;

int n,a,b,Map[N][N],Max[N][N],Min[N][N],ans=1e9+5;

inline int read()

{

    int X=0,w=1; char ch=0;

    while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();

    return X*w;

}

int main()

{

    cin>>a>>b>>n;

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

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

        Map[i][j]=read();

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

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

        {

            int Mx=0,Mi=1e9+5;

            for(int k=0;k<n;++k)

            {

                Mx=max(Mx,Map[i][j+k]);

                Mi=min(Mi,Map[i][j+k]);

            }

            Max[i][j]=Mx;

            Min[i][j]=Mi;

        }

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

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

        {

            int Mx=0,Mi=1e9+5;

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

            {

                Mx=max(Mx,Max[k][j]);

                Mi=min(Mi,Min[k][j]);

            }

            ans=min(Mx-Mi,ans);

        }

    cout<<ans;

    return 0;

}

巴特西

洛谷 2216 [HAOI2007]理想的正方形

最新文章

热门文章