当前位置:网站首页>Acwing 1091. Ideal square

Acwing 1091. Ideal square

2021-03-08 13:17:31 glm233

For this problem, we can find the sliding window of each line Then put it in the last position of the window Finally, the column's sliding window is compressed The maximum value and the minimum value are made once respectively Traversing through the preprocessed array of maximum and minimum values Just update the answer

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,k,a[N][N],ans_min[N][N],ans_max[N][N];
void getmin(int a[],int b[],int n){
    deque<int>q;
    for(int i=1;i<=n;i++){
        if(!q.empty()&&i-q.front()>=k)q.pop_front();
        while(!q.empty()&&a[q.back()]>=a[i])q.pop_back();
        q.push_back(i);
        b[i]=a[q.front()];
    }
}
void getmax(int a[],int b[],int n){
    deque<int>q;
    for(int i=1;i<=n;i++){
        if(!q.empty()&&i-q.front()>=k)q.pop_front();
        while(!q.empty()&&a[q.back()]<=a[i])q.pop_back();
        q.push_back(i);
        b[i]=a[q.front()];
    }
}
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
    }
    for(int i=1;i<=n;i++){
        getmin(a[i],ans_min[i],m),getmax(a[i],ans_max[i],m);
        /*for(int j=1;j<=m;j++){
            cout<<ans_min[i][j]<<" ";
        }
        cout<<endl;*/
    }
    int ans=INT_MAX,tepa[N],tarb[N],tarc[N];
    for(int i=k;i<=m;i++){
        for(int j=1;j<=n;j++){
            tepa[j]=ans_min[j][i];
        }
        getmin(tepa,tarb,n);
        for(int j=1;j<=n;j++){
            tepa[j]=ans_max[j][i];
        }
        getmax(tepa,tarc,n);
        for(int j=k;j<=n;j++)ans=min(ans,tarc[j]-tarb[j]);
    }
    cout<<ans<<endl;
}

Participation of this paper Tencent cloud media sharing plan , You are welcome to join us , share .

版权声明
本文为[glm233]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/03/20210308123603733s.html