Luogu 2216 [HAOI2007]理想的正方形 (单调队列优化)
2024-10-20 03:18:26
题意:
给出一个 N×M 的矩阵,以及一个数值 K ,求在给定的矩阵中取出一个 K×K 的矩阵其中最大值减去最小值的最小值。
细节:
没有细节来发暴力走天下,20分也是分啊~~~ QAQ。
分析:
感觉是一题裸体,大佬们看了一定秒切,但是本蒟蒻显然不会,二维不易可以先尝试如何求解在 1×K 的矩阵中求解答案呢,显然是利用一个数组 Max1[i][j] 表示第 i 行区间 [ j , j + K - 1] 的最大值,Min1[i][j] 表示第 i 行区间 [ j , j + K - 1] 的最小值,每行利用一个单调队列进行定区间求最值的操作,最后 O(N×M) 的枚举所有的 1×K 的矩阵,求解最小值即可。
好吧此时你应该豁然开朗,这(TM <- 希望忽略这个东西)就是将一维的数组在进行一次求解,得到二维数组的最值即可,仍然利用一个数组 Max2[i][j] 表示纵向区间 [i , i + K - 1]、横向区间 [j , j + K - 1]中的最大值,Min2[i][j] 表示纵向区间 [i , i + K - 1]、横向区间 [j , j + K - 1]中的最小值,只需要对上面一步操作的中的 Max1[][]、Min1[][]数组,每列利用一个单调队列进行定区间求最值,同样是 O(N×M) 的时间复杂度处理出了所有 K×K 的矩阵,最后只需要统计答案所指向的最优值即可。
实际上本题也是含有少许 Dp 的思想,将大多的重复与不必要同过单调队列的思想进行了优化,这应该是一道不错的练手的模板题。
代码:
#include<cstdio>
#include<iostream>
using namespace std;
int n,m,k,front,FRONT,back,BACK,ans;
int a[][],q[],Q[],x[][],X[][],y[][],Y[][];
int main()
{
scanf("%d%d%d",&n,&m,&k);
for (int I=;I<=n;I++)
for (int i=;i<=m;i++)
scanf("%d",&a[I][i]);
for (int I=;I<=n;I++){
FRONT=BACK=front=back=Q[]=q[]=;
for (int i=;i<=m;i++){
while (a[I][i]>=a[I][Q[BACK]]&&FRONT<=BACK) BACK--;
while (a[I][i]<=a[I][q[back]]&&front<=back) back--;
BACK++;back++;Q[BACK]=i;q[back]=i;
while (i-Q[FRONT]>=k) FRONT++;
while (i-q[front]>=k) front++;
if (i>=k) X[I][i-k+]=a[I][Q[FRONT]],x[I][i-k+]=a[I][q[front]];
}
}
for (int I=;I<=m-k+;I++){
FRONT=BACK=front=back=Q[]=q[]=;
for (int i=;i<=n;i++){
while (X[i][I]>=X[Q[BACK]][I]&&FRONT<=BACK) BACK--;
while (x[i][I]<=x[q[back]][I]&&front<=back) back--;
BACK++;back++;Q[BACK]=i;q[back]=i;
while (i-Q[FRONT]>=k) FRONT++;
while (i-q[front]>=k) front++;
if (i>=k) Y[i-k+][I]=X[Q[FRONT]][I],y[i-k+][I]=x[q[front]][I];
}
}
ans=0x3f3f3f3f;
for (int I=;I<=n-k+;I++)
for (int i=;i<=m-k+;i++) ans=min(ans,Y[I][i]-y[I][i]);
printf("%d\n",ans);
return ;
}
咳咳,此代码代码风格奇异,可能不是原创,请各位阅读者谅解…… QWQ。
最新文章
- A 浪哥的烦恼 完全背包dp
- oracle11g客户端 安装图解
- Linux 文件系统错误的修复方法 ddrescue替代dd的恢复软件 备用超级块
- 《Java程序设计》第三周学习总结
- Java容器类接口:Iterator,Collection,Map
- STL容器迭代器失效分析
- creating normals from alpha/heightmap inside a shader
- PowerDesigner 怎么给 Table Properties 增加注释和默认值
- c语言学习之第四章
- Apache 2.4.7在CentOS6.4中安装配置反向代理解决单外网IP对应多个内网主机的方法实践
- Xamarin开发笔记—WebView双项事件调用
- phpstudy如何安装景安ssl证书 window下apache服务器网站https访问
- 前端开发 JavaScript 规范文档
- AsyncTask 进行耗时操作和UI 更新
- 11.redis_python
- hdu-1036(格式题+精确度)
- Atcoder Grand 006 C-Rabbit Exercise
- 玩转ptrace(转)
- 第六次ScrumMeeting博客
- 软工第十二周个人PSP
热门文章
- 普通平衡树与文艺平衡树的splay代码
- ERP实施顾问,请找准自己的定位
- eclipse导入mavn工程报Failure to transfer org.apache.maven.plugins:maven-resources-plugin:pom:2.6 的解决办法
- rsync服务的安装与配置
- jQuery position() 源码解读
- No bean named &#39;springSecurityFilterChain&#39; is defined
- cf559C. Gerald and Giant Chess(容斥原理)
- JavaScript30-7 数组的一些基本方法
- ReactiveCocoa 响应式函数编程
- IOS实现弹出菜单效果MenuViewController(背景 景深 弹出菜单)