题目描述
给定一个wh的矩形，每个方格内有数，求一个nn的正方形，使得正方形内部最小值加最大值的值最小。
你只需要输出这个数值
输入格式
第一行三个正整数w,h,n w,h <=2000,n <=min(w,h)
接下来w行每行h个数描述这个矩阵，保证矩阵中所有数非负并且不超过1e9
输出格式
一个整数.
样例输入
5 4 2 1 2 5 6 0 17 16 0 16 17 2 1 2 10 2 1 1 2 2 2
样例输出
3
约定
对于10%的数据，max(w,h)<=10
对于20%的数据，max(w,h)<=100
对于40%的数据，max(w,h)<=500
对于60%的数据，max(w,h)<=1000
对于100%的数据，max(w,h)<=2000
TLE70分代码
#include<bits/stdc++.h>
using namespace std;
int w,h,n,ans=INT_MAX,a[20005][20005];
int check(int x,int y){
int minn=INT_MAX,maxx=INT_MIN;
for(int i=x-n+1;i<=x;i++){
for(int j=y-n+1;j<=y;j++){
maxx=max(maxx,a[i][j]);
minn=min(minn,a[i][j]);
}
}
return maxx+minn;
}
int main(){
cin>>w>>h>>n;
for(int i=1;i<=w;i++){
for(int j=1;j<=h;j++){
cin>>a[i][j];
}
}
for(int i=n;i<=w;i++){
for(int j=n;j<=h;j++){
ans=min(ans,check(i,j));
}
}
cout<<ans<<endl;
return 0;
}