没有复杂结构甚至不长但是写起来就很想死的代码类型

原理非常简单,就是用先用单调队列处理出mn1[i][j]表示i行的j到j+k-1列的最小值,mx1[i][j]表示i行的j到j+k-1列的最大值

然后就变成求单列最大最小值,用上面同样的方法处理出对于列的mn2mx2即可

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1005;
int n,m,k,a[N][N],mn1[N][N],mx1[N][N],mn2[N][N],mx2[N][N],ans=1e9,q1[N],l1,r1,q2[N],l2,r2;
int read()
{
int r=0,f=1;
char p=getchar();
while(p>'9'||p<'0')
{
if(p=='-')
f=-1;
p=getchar();
}
while(p>='0'&&p<='9')
{
r=r*10+p-48;
p=getchar();
}
return r*f;
}
int main()
{
n=read(),m=read(),k=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a[i][j]=read();
for(int i=1;i<=n;i++)
{
l2=r2=l1=r1=q2[1]=q1[1]=1;
for(int j=2;j<=m;j++)
{
while(a[i][j]>=a[i][q2[r2]]&&l2<=r2)
r2--;
while(a[i][j]<=a[i][q1[r1]]&&l1<=r1)
r1--;
q2[++r2]=j;q1[++r1]=j;
while(j-q2[l2]>=k)
l2++;
while(j-q1[l1]>=k)
l1++;
if(j>=k)
mx1[i][j-k+1]=a[i][q2[l2]],mn1[i][j-k+1]=a[i][q1[l1]];
}
}
for (int j=1;j<=m-k+1;j++)
{
l2=r2=l1=r1=q2[1]=q1[1]=1;
for(int i=2;i<=n;i++)
{
while(mx1[i][j]>=mx1[q2[r2]][j]&&l2<=r2)
r2--;
while(mn1[i][j]<=mn1[q1[r1]][j]&&l1<=r1)
r1--;
q2[++r2]=i;q1[++r1]=i;
while(i-q2[l2]>=k)
l2++;
while(i-q1[l1]>=k)
l1++;
if(i>=k)
mx2[i-k+1][j]=mx1[q2[l2]][j],mn2[i-k+1][j]=mn1[q1[l1]][j];
}
}
for(int i=1;i<=n-k+1;i++)
for(int j=1;j<=m-k+1;j++)
ans=min(ans,mx2[i][j]-mn2[i][j]);
printf("%d\n",ans);
return 0;
}

最新文章

  1. Linux下定时执行脚本(转自Decode360)
  2. koa知识点
  3. 《高可用MySQL》1 – Windows环境下压缩版MySQL安装
  4. Effective C++ -----条款32:确定你的public继承塑模出is-a关系
  5. PHP CURL实现远程下载文件到本地
  6. HDU-3436 Queue-jumpers 树状数组 | Splay tree删除,移动
  7. 《Effect Java》学习笔记1———创建和销毁对象
  8. HBase技术介绍
  9. EffectiveC#6--区别值类型数据和引用类型数据
  10. Unity 制作RPG地图2(自己控制地图上图标)
  11. Hibernate3 第三天
  12. layui表格点击排序按钮后,表格绑定事件失效解决方法
  13. Cisco交换机设置备份
  14. python中lambda表达式中自由变量的坑,因为for循环结束了 变量还保存着,详见关于for循环的随笔
  15. Oozie分布式工作流——EL表达式
  16. 如何解决python连接数据库编码问题(python传数据到mysql乱码)&#39;ascii&#39; codec can&#39;t encode _mysql_exceptions.OperationalError: (1366, &quot;Incorrect string value:?
  17. window的一些属性
  18. java-jdk7-forkjoin异常返回
  19. Python(二)列表的增删改查
  20. 20172321『Java程序设计』课程 结对编程练习_四则运算第二周阶段总结

热门文章

  1. 【转】WEB前端调优
  2. C51 蜂鸣器 个人笔记
  3. Codeforces 651A Joysticks【贪心】
  4. dataTables 添加行内操作按钮
  5. Windows上安装Mac OS
  6. centos7容量扩充
  7. C#如何把写好的类编译成dll文件
  8. VS打包部署图文具体步骤及程序防卸载的制作(password验证卸载)
  9. Mahout贝叶斯算法拓展篇3---分类无标签数据
  10. NPOI2.2.0.0实例详解(十)—设置EXCEL单元格【文本格式】 NPOI 单元格 格式设为文本 HSSFDataFormat