bzoj 1047: [HAOI2007]理想的正方形【单调队列】
2024-10-20 06:36:45
没有复杂结构甚至不长但是写起来就很想死的代码类型
原理非常简单,就是用先用单调队列处理出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;
}
最新文章
- Linux下定时执行脚本(转自Decode360)
- koa知识点
- 《高可用MySQL》1 – Windows环境下压缩版MySQL安装
- Effective C++ -----条款32:确定你的public继承塑模出is-a关系
- PHP CURL实现远程下载文件到本地
- HDU-3436 Queue-jumpers 树状数组 | Splay tree删除,移动
- 《Effect Java》学习笔记1———创建和销毁对象
- HBase技术介绍
- EffectiveC#6--区别值类型数据和引用类型数据
- Unity 制作RPG地图2(自己控制地图上图标)
- Hibernate3 第三天
- layui表格点击排序按钮后,表格绑定事件失效解决方法
- Cisco交换机设置备份
- python中lambda表达式中自由变量的坑,因为for循环结束了 变量还保存着,详见关于for循环的随笔
- Oozie分布式工作流——EL表达式
- 如何解决python连接数据库编码问题(python传数据到mysql乱码)&#39;ascii&#39; codec can&#39;t encode _mysql_exceptions.OperationalError: (1366, ";Incorrect string value:?
- window的一些属性
- java-jdk7-forkjoin异常返回
- Python(二)列表的增删改查
- 20172321『Java程序设计』课程 结对编程练习_四则运算第二周阶段总结