题目:

给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 ;
}

最新文章

  1. C#中Length和Count的区别(个人观点)
  2. Linux下PHP+MYSQL+APACHE配置方法
  3. iOS ---Extension编程指南
  4. Android表情功能
  5. 基于jquery框架的ajax搜索显示
  6. apache开源项目 --Struts
  7. php 图片等比缩放
  8. SpringMVC表单中post请求转换为put或delete请求
  9. 接口测试——Java + TestNG 国家气象局接口(json解析)实例
  10. AM335x(TQ335x)学习笔记——USB驱动移植
  11. LeetCode算法题-Kth Largest Element in a Stream(Java实现)
  12. k8s的flannel的pod运行一段时间init error
  13. February 20th, 2018 Week 8th Tuesday
  14. get_or_create函数
  15. 20165228 实验一 Java开发环境的熟悉
  16. 利用javascript实现css操作
  17. bug排查
  18. 【转】WireShark 过滤规则
  19. IDEA创建maven项目jar更新缓慢问题
  20. StreamSets Data Collector Edge 说明

热门文章

  1. Java子类与父类之间的类型转换
  2. C#监听锁屏代码
  3. tomcat6升级到7时400问题,以及url带有汉字时出错。
  4. Linux用户切换和密码修改
  5. 180620-mysql之数据库导入导出
  6. List和Turple
  7. linux下的java开发环境
  8. 前端开发工程师 - 02.JavaScript程序设计 - 第1章.基础篇
  9. 在deepin系统中制作桌面快捷方式
  10. Java并发基础--Lock的学习