题面
先把题目意思讲一下吧:
给一个 (n*n) 的地图,每个格子有一个价格,找一个矩形区域,使其价格总和位于([k,2k]).
那么首先,可以想到,如果(a[i][j])(格子的价格,下同)位于([k,2k]),直接输出就好.
而对于(a[i][j])>(2k)的格子,它是不可能被选的,那么可以把它视为障碍物,
然后,剩下的格子的价格就一定小于(k).
那么,根据悬线法,
如果我们找到了一个极大子矩阵,且矩阵和(设为(sum))>=(k)(小于肯定是不行的),
如果(sum)<=(2k),就直接输出答案,
否则,判断第一行的和(sum_{1}),
若(sum_{1})>=(k),那在第一行中肯定有解,
因为每个元素都小于(k)(前面说过了),
那么不存在一个格子能使矩阵和从大于(2k)一下变到小于(k),
因此只需要一个个删掉第一行的元素,直到符合要求即可.
而当(sum_{1})<(k)时,
因为(sum)>(2k),
所以可以删掉第一行,再继续判断剩下的矩阵.
这一部分的实现方式:
inline void print_t(int x1,int y1,int x2,int y2)/*以(x1,y1)为左上角,(x2,y2)为右下角*/{
while(sum(x1,y1,x2,y2)/*矩阵和*/>m*2){
if(x1==x2) y2--;
else if(sum(x1,y1,x1,y2)>=m) x2=x1;
else x1++;
}
printf("%d %d %d %d
",y1,x1,y2,x2);
exit(0);//终止程序
}
最后注意:找到答案后直接终止程序!
上完整代码:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
int sum=0,f=1;char ch=getchar();
while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
return f*sum;
}
int n,m;
ll a[2001][2001];//价格
ll s[2001][2001];//二维前缀和
int h[2001][2001]/*悬线*/,l[2001][2001]/*向左展开的位置*/,r[2001][2001]/*向右展开的位置*/;
inline ll sum(int x1,int y1,int x2,int y2)/*矩阵和*/{
return s[x2][y2]+s[x1-1][y1-1]-s[x1-1][y2]-s[x2][y1-1];
}
inline void print_t(int x1,int y1,int x2,int y2){
while(sum(x1,y1,x2,y2)>m*2){
if(x1==x2) y2--;
else if(sum(x1,y1,x1,y2)>=m) x2=x1;
else x1++;
}
printf("%d %d %d %d
",y1,x1,y2,x2);
exit(0);
}
int main(){
// freopen("kup.in","r",stdin);
// freopen("kup.out","w",stdout);
m=read();n=read();//m就是k,只是看上去顺眼一些而已[滑稽]
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
a[i][j]=read();
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
if(a[i][j]<m||a[i][j]>2*m) continue;
printf("%d %d %d %d
",j,i,j,i);
return 0;
}
for(int i=1;i<=n;i++) r[0][i]=n+1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) h[i][j]= a[i][j]>2*m? 0:h[i-1][j]+1;
for(int i=1;i<=n;i++){
int ret=0;
for(int j=1;j<=n;j++){
if(h[i][j]) l[i][j]=max(l[i-1][j],ret);
else ret=j,l[i][j]=0;
}
ret=n+1;
for(int j=n;j;j--){
if(h[i][j]) r[i][j]=min(r[i-1][j],ret);
else ret=j,r[i][j]=n+1;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(!h[i][j]) continue;
int x1=i-h[i][j]+1;
int y1=l[i][j]+1,y2=r[i][j]-1;
if(sum(x1,y1,i,y2)<m) continue;
print_t(x1,y1,i,y2);
}
}
puts("NIE");
return 0;
}