bzoj1047 [HAOI2007]理想的正方形——二维单调队列
2024-08-24 09:13:55
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=1047
就是先对行做一遍单调队列,再对那个结果按列做一遍单调队列即可。
代码如下:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int const maxn=;
int a,b,n,m[maxn][maxn],hmn[maxn][maxn],mn,hmx[maxn][maxn],mx;
int w[maxn],qmn[maxn],qmx[maxn],headn,tailn,headx,tailx,ans;
int main()
{
scanf("%d%d%d",&a,&b,&n);
for(int i=,x;i<=a;i++)
{
headn=;tailn=;headx=;tailx=;//
for(int j=;j<=b;j++)
{
scanf("%d",&w[j]);int x=w[j];
if(j-qmn[headn]>=n)headn++;//位置而非个数
if(j-qmx[headx]>=n)headx++;
while(headn<=tailn&&x<=w[qmn[tailn]])tailn--;
while(headx<=tailx&&x>=w[qmx[tailx]])tailx--;
qmn[++tailn]=j;qmx[++tailx]=j;//
hmn[i][j]=w[qmn[headn]];hmx[i][j]=w[qmx[headx]];
}
}
ans=1e9;
for(int j=;j<=b;j++)
{
headn=;tailn=;headx=;tailx=;
for(int i=;i<=a;i++)
{
int x=hmn[i][j],y=hmx[i][j];
if(i-qmn[headn]>=n)headn++;//
if(i-qmx[headx]>=n)headx++;
while(headn<=tailn&&x<=hmn[qmn[tailn]][j])tailn--;
while(headx<=tailx&&y>=hmx[qmx[tailx]][j])tailx--;
qmn[++tailn]=i;qmx[++tailx]=i;
mn=hmn[qmn[headn]][j];mx=hmx[qmx[headx]][j];
if(i<n||j<n)continue;//||
ans=min(ans,mx-mn);
}
}
printf("%d",ans);
return ;
}
最新文章
- 子DIV设置margin-top影响父DIV位置的解决办法
- yield生成器及字符串的格式化
- Yii 框架学习--02 进阶
- css字体家族
- [转]Asp.net MVC 利用PartialView 构造自定义菜单
- c++ 指针(二)
- Using Interface Builder记录
- UVa 11536 Smallest Sub-Array (水题, 滑动窗口)
- Linux之apt-get无sudo权限安装软件
- Python常用模块的安装方法
- java打jar包 命令行cmd在当前路径打jar包
- [LeetCode] Reshape the Matrix 重塑矩阵
- ARM linux常用汇编语法
- idea之debug
- 纯js Ajax 请求
- keepalive高可用
- Github的建立及心得体会
- Apater适配器模式(结构型模式)
- js-ES6学习笔记-Generator函数的应用
- opencv图片右转函数