P2216 [HAOI2007]理想的正方形方法记录( 二 ) _生活百科

然后只需要遍历一遍，求出最小的\(y2[i][j]-y1[i][j]\)即可。
#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>using namespace std;const int N=1005;int a,b,n;int board[N][N];int x1[N][N],x2[N][N],y1[N][N],y2[N][N];int q1[N],q2[N];int cntx1,cntx2,cnty1,cnty2;int minn(int a,int b){ return a<b?a:b;}int ans=2147483647;int main(){ scanf("%d%d%d",&a,&b,&n); for(int i=1;i<=a;i++)for(int j=1;j<=b;j++)scanf("%d",&board[i][j]); for(int i=1;i<=a;i++) {int h=0,t=0;memset(q1,0,sizeof(q1));memset(q2,0,sizeof(q2));for(int j=1;j<=b;j++){while(h<=t&&j-q1[h]>=n) h++;while(h<=t&&board[i][j]<board[i][q1[t]]) t--;q1[++t]=j;if(j>=n) x1[i][j-n+1]=board[i][q1[h]];}for(int j=1;j<=b;j++){while(h<=t&&j-q2[h]>=n) h++;while(h<=t&&board[i][j]>board[i][q2[t]]) t--;q2[++t]=j;if(j>=n) x2[i][j-n+1]=board[i][q2[h]];} } memset(q1,0,sizeof(q1)); memset(q2,0,sizeof(q2)); for(int i=1;i<=b-n+1;i++) {int h=0,t=0;memset(q1,0,sizeof(q1));memset(q2,0,sizeof(q2));for(int j=1;j<=a;j++){while(h<=t&&j-q1[h]>=n) h++;while(h<=t&&x1[j][i]<x1[q1[t]][i]) t--;q1[++t]=j;if(j>=n) y1[j-n+1][i]=x1[q1[h]][i];}for(int j=1;j<=a;j++){while(h<=t&&j-q2[h]>=n) h++;while(h<=t&&x2[j][i]>x2[q2[t]][i]) t--;q2[++t]=j;if(j>=n) y2[j-n+1][i]=x2[q2[h]][i];} } for(int i=1;i<=a-n+1;i++)for(int j=1;j<=b-n+1;j++)ans=minn(ans,y2[i][j]-y1[i][j]); printf("%d\n",ans); return 0;}

P2216 [HAOI2007]理想的正方形方法记录( 二 )

经验总结扩展阅读

爸爸经常打骂孩子怎么办

好听聚财的公司名字聚人聚财的企业名字

再过4天，鸿运当头，高人一等，喜事接踵，横财不断，尽享富贵

亚麻衣服怎么洗不缩水,亚麻面料的衣服这样清洗不会缩水？

仲孙姓男孩起名大全

纱窗拐角断了如何取出来纱窗拐角断了用什么取代

宝宝成长中的几个关键时期--1岁以内宝宝

11年奇瑞瑞虎油耗多少?

开封清明上河园什么时候开门

导语：心仪的他就在眼前心仪的男人不唐突的4种搭讪方式，教你把握机会，迈出追爱第一步

疾病 40岁是肠道疾病“高发期”，若想肠道更健康，3个坏习惯要改掉

谈谈学生早恋的危害不要让自己抱憾终生

夏季肌肤护理必知化妆水如何使用

二十四史有哪些,二十四史有哪些

象鼻山公园旅游攻略掌握三点就可以

六款2023年最佳手机推荐手机好用排行榜2023

韩国眉毛的画法这几个技巧你要知道

巴奴是哪里的品牌

2022年10月24日是出火的黄道吉日吗 2022年农历九月廿九宜出火吗

海蛎子能放几天,生海蛎子能放多长时间