注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 3530  

2012-07-23 09:28:27|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
刚开始做的时候,就用了一个单调队列,但是总感觉有问题,打出来后叫上去果然WA了
后来看到网上大家都是拿了两个单调队列做,仔细想了之后发现很有道理,没有破绽
一个单调队列存最大值,即队列里是递减的,队首最大;一个单调队列里存最小值,即队列里是递增的,队首最小
插入的元素依次在两个队列里找到合适的位置,从后面开始遍历,如果比其小(大),则舍弃

/*
* fudq.cpp
*
* Created on: 2012-07-19
* Author: fudq
*/
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#include<iomanip>
#include<string>
#include<string.h>
#include<math.h>
#include<queue>
#include<map>
#include<stack>
#include<iostream>
using namespace std;
#define N 100010
int num[N],q1[N],q2[N];
int max(int a ,int b)
{
return a>b?a:b;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
#endif
int n,m,k,i,res,f1,f2,t1,t2,last1,last2;
while(scanf("%d%d%d",&n,&m,&k)!=EOF)
{
for(i=1;i<=n;i++)
scanf("%d",&num[i]);
res=0;f1=0;f2=0;t1=0;t2=0;last1=0;last2=0;
for(i=1;i<=n;i++)
{
//max
while(f1<t1 && num[i] >= num[q1[t1-1]])
t1--;
q1[t1++]=i;

//min
while(f2<t2 && num[i] <= num[q2[t2-1]])
t2--;
q2[t2++]=i;

while(num[q1[f1]]-num[q2[f2]] > k)
{
if(q1[f1]<q2[f2])
last1=q1[f1++];
else
last2=q2[f2++];
}
if(num[q1[f1]]-num[q2[f2]] >= m)
res=max(res,i-max(last1,last2));
}
printf("%d\n",res);
}
return 0;
}


  评论这张
 
阅读(162)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018