BZOJ2096:[POI2010]Pilots
2024-08-26 19:37:39
浅谈队列:https://www.cnblogs.com/AKMer/p/10314965.html
题目传送门:https://lydsy.com/JudgeOnline/problem.php?id=2096
尺取法,详见这篇博客:https://www.cnblogs.com/AKMer/p/10323600.html
不过这次我们要统计的区间越长越好。
所以我们需要在最大值减最小值不超过给定的\(k\)的情况下尽量让左端点靠左。
用一个单调队列维护区间最大值,另一个单调队列维护区间最小值。
如果最大值减最小值大于\(k\)那么把位置靠前的那个值弹出队列,那个位置的后边一个就是新的左端点。
时间复杂度:\(O(n)\)
空间复杂度:\(O(n)\)
代码如下:
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=3e6+5;
int a[maxn],list1[maxn],list2[maxn];
int n,k,ans,pos,head1,tail1,head2,tail2;
int read() {
int x=0,f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
return x*f;
}
int main() {
k=read(),n=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=n;i++) {
while(head1!=tail1&&a[list1[tail1-1]]<=a[i])tail1--;
list1[tail1++]=i;
while(head2!=tail2&&a[list2[tail2-1]]>=a[i])tail2--;
list2[tail2++]=i;
while(a[list1[head1]]-a[list2[head2]]>k) {
if(list1[head1]<list2[head2])pos=list1[head1++];
else pos=list2[head2++];
}
ans=max(ans,i-pos);
}
printf("%d\n",ans);
return 0;
}
最新文章
- easyui如何动态改变列的编辑属性
- Atitit常见的标准化组织与规范数量jcp ecma&#160;iso
- Ubuntu 12.4 Apache2 安装教程
- Javascript初学篇章_1(概念/数据类型)
- Uva442 hdu 1082 Matrix Chain Multiplication
- 第十三周学习笔记(编辑器选错了重发了这一个 原博客的确周天晚上提交了orz)
- JAX-WS(三)构建简单webservice部署到tomcat上
- JavaScript经典代码【一】【javascript HTML控件获取值】
- ENVI如何打开IRS P6的AWIFS的ges及LISS3的ges文件?
- 解决VS2012【加载......符号缓慢】的问题
- Nginx高并发配置思路(轻松应对1万并发量)
- IOS 新消息通知提示-声音、震动
- 如何安装chrome扩展?比如json-handle插件如何安装
- JS基础——循环很重要
- SCP“免密” 远程COPY较多文件
- 类 Arrays StringBuilder 跟 StringBuffer 的异同 SimpleDateFormat
- 磨人的Fragment的转换
- 转:Python: 什么是*args和**kwargs
- hive数学函数
- c#代码混淆
热门文章
- C++ IPv4与IPv6的兼容编码(转,出自http://blog.csdn.net/ligt0610/article/details/18667595)
- Linux基础四---系统监控&;硬盘分区
- pagination结合ajax
- 重定向【TLCL】
- iframe标签的子父页面调用函数和属性
- nova Flavors
- html5 frameset5内嵌框架集
- ebs R12 支持IE11
- js抛物线
- LeetCode OJ:Binary Search Tree Iterator(二叉搜索树迭代器)