【bzoj1047】[HAOI2007]理想的正方形

2015.05.25 11:34 Mon | 15次阅读 | 旧日oi | 固定链接 | 源码

题目大意:有一个a*b的整数组成的矩阵,现请你从中找出一个n*n的正方形区域,使得该区域所有数中的最大值和最小值的差最小。a,b<=1000,n<=100
题解:
我的做法比较渣,用得set,貌似单调队列可以去掉那个log,话说单调队列的题我经常写成set……
对每个点维护上面包括自己在内的上方n个点的最大值和最小值,这里用一遍set,按顺序横着扫描,每次把包含自己在内的左面n个点的最大值和最小值扔到set里就行了。
本人代码5000+ms,单调队列貌似1s就可以了……

我的程序

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
int a,b,n;
int x[1005][1005],mx[1005][1005],mn[1005][1005];
multiset<int> s;
int main()
{
    cin>>a>>b>>n;
    for(int i=1;i<=a;i++)
    for(int j=1;j<=b;j++)
        scanf("%d",&x[i][j]);
    for(int i=1;i<=b;i++)
    {
        s.clear();
        for(int j=1;j<=n;j++) 
        s.insert(x[j][i]);
        mx[n][i]=*s.rbegin();
        mn[n][i]=*s.begin();
        for(int j=n+1;j<=a;j++) 
        {
            s.insert(x[j][i]);
            s.erase(s.find(x[j-n][i]));
            mx[j][i]=*s.rbegin();
            mn[j][i]=*s.begin();
        }
    }
    int ans=0x3f3f3f3f;
    for(int i=n;i<=a;i++)
    {
        s.clear();
        for(int j=1;j<=n;j++) s.insert(mx[i][j]),s.insert(mn[i][j]);
        ans=min(ans,*s.rbegin()-*s.begin());
        for(int j=n+1;j<=b;j++) 
        {
            s.insert(mx[i][j]);s.insert(mn[i][j]);
            s.erase(s.find(mx[i][j-n]));s.erase(s.find(mn[i][j-n]));
            ans=min(ans,*s.rbegin()-*s.begin());
        }
    }
    cout<<ans<<endl;
}```