BZOJ 1342: [Baltic2007]Sound静音问题 | 单调队列维护的好题
2024-09-04 17:35:29
题目:
给n个数字,一段合法区间[l,l+m-1]要求max-min<=c
输出所有合法区间的左端点,如果没有输出NONE
题解:
单调队列同时维护最大值和最小值
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 1000005
using namespace std;
int n,m,c,Q[N],q[N],a[N],Ql,Qr,ql,qr,OK;
int main()
{
scanf("%d%d%d",&n,&m,&c);
for (int i=;i<=n;i++)
scanf("%d",a+i);
q[]=Q[]=;
for (int i=;i<=n;i++)
{
while (Ql<=Qr && Q[Ql]<=i-m) Ql++;
while (ql<=qr && q[ql]<=i-m) ql++;
while (Ql<=Qr && a[Q[Qr]]<a[i]) Qr--;Q[++Qr]=i;
while (ql<=qr && a[q[qr]]>a[i]) qr--;q[++qr]=i;
if (a[Q[Ql]]-a[q[ql]]<=c && i>=m) OK=,printf("%d\n",i-m+);
}
if (!OK) puts("NONE");
return ;
}
最新文章
- C#中Length和Count的区别(个人观点)
- Linux下PHP+MYSQL+APACHE配置方法
- iOS ---Extension编程指南
- Android表情功能
- 基于jquery框架的ajax搜索显示
- apache开源项目 --Struts
- php 图片等比缩放
- SpringMVC表单中post请求转换为put或delete请求
- 接口测试——Java + TestNG 国家气象局接口(json解析)实例
- AM335x(TQ335x)学习笔记——USB驱动移植
- LeetCode算法题-Kth Largest Element in a Stream(Java实现)
- k8s的flannel的pod运行一段时间init error
- February 20th, 2018 Week 8th Tuesday
- get_or_create函数
- 20165228 实验一 Java开发环境的熟悉
- 利用javascript实现css操作
- bug排查
- 【转】WireShark 过滤规则
- IDEA创建maven项目jar更新缓慢问题
- StreamSets Data Collector Edge 说明