题目描述
有一个 a*b 的整数组成的矩阵, 现请你从中找出一个 n*n 的正方形区域, 使得该区域所有数中的最大值和最小值
的差最小.
输入
第一行为 3 个整数, 分别表示 a,b,n 的值第二行至第 a+1 行每行为 b 个非负整数, 表示矩阵中相应位置上的数. 每
行相邻两数之间用一空格分隔.
100% 的数据 2<=a,b<=1000,n<=a,n<=b,n<=1000
输出
仅一个整数, 为 a*b 矩阵中所有 "n*n 正方形区域中的最大整数和最小整数的差值" 的最小值.
样例输入
- Copy 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
样例输出
- Copy Sample Output
- 1
分析: 学习大佬算法, 单调队列能这么简单可还行.
- #include <iostream>
- #include <string>
- #include <cstdio>
- #include <cmath>
- #include <cstring>
- #include <algorithm>
- #include <vector>
- #include <queue>
- #include <deque>
- #include <map>
- #define range(i,a,b) for(int i=a;i<=b;++i)
- #define LL long long
- #define rerange(i,a,b) for(int i=a;i>=b;--i)
- #define fill(arr,tmp) memset(arr,tmp,sizeof(arr))
- using namespace std;
- int a,b,n,tt[1005][1005],gg[1005][1005],mm[2][1005][1005];
- pair<int,int>q[1005];
- void init(){
- cin>>a>>b>>n;
- range(i,1,a)range(j,1,b)cin>>tt[i][j];
- }
- void cal(int x){
- range(i,1,a){
- int left=1,right=0;
- range(j,1,b){
- while(left<=right&&j-q[left].second>=n)++left;
- if(!x)while(left<=right&&tt[i][j]>=q[right].first)--right;
- else while(left<=right&&tt[i][j]<=q[right].first)--right;
- q[++right]=make_pair(tt[i][j],j);
- gg[i][j]=q[left].first;
- }
- }
- range(j,n,b){
- int left=1,right=0;
- range(i,1,a){
- while(left<right&&i-q[left].second>=n)++left;
- if(!x)while(left<=right&&gg[i][j]>=q[right].first)--right;
- else while(left<=right&&gg[i][j]<=q[right].first)--right;
- q[++right]=make_pair(gg[i][j],i);
- mm[x][i][j]=q[left].first;
- }
- }
- }
- void solve(){
- cal(0);cal(1);
- int ans=1<<30;
- range(i,n,a)
- range(j,n,b)ans=min(ans,mm[0][i][j]-mm[1][i][j]);
- cout<<ans<<endl;
- }
- int main() {
- init();
- solve();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2692466.html