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

那一日,泪水打湿雪花冰冷的心

曾经的滋味,回忆在一次次的离合中,回眸时,那一刻,如涟漪般在一刹那融化

 
 
 

日志

 
 

POJ 2823  

2010-06-24 08:49:00|  分类: poj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这个题用单调队列可以达到O(n)的平摊效率。
单调队列的维护一个有序的队列,比如一个非降序列,然后从后面插值,如果新的值比末尾的大,就把末尾的弹出,取值时从头开始取,看是否满足标号,如果不满足则去下一个。
顺便一提,这题竟然会卡scanf和printf,于是用getchar和puchar之后时间瞬间达到一秒以内
#include<cstdio>
int a[1000001][2],b[1000001][2],n,m,k,f1,t1,f2,t2,c[1000001];
inline void addmin(int x,int y){
while(t1>=f1&&a[t1][0]>x)
--t1;
++t1;
a[t1][0]=x;
a[t1][1]=y;
}
inline void addmax(int x,int y){
while(t2>=f2&&b[t2][0]<x)
--t2;
++t2;
b[t2][0]=x;
b[t2][1]=y;
}
inline int getmin(int x){
while(a[f1][1]<x)
++f1;
return a[f1][0];
}
inline int getmax(int x){
while(b[f2][1]<x)
++f2;
return b[f2][0];
}
inline bool readint(int &ret)
{
int sgn;
char c;
c=getchar();
if(c==EOF)return false;
while(c!='-'&&c<'0'||c>'9')c=getchar();
sgn=(c=='-')?-1:1;
ret=(c=='-')?0:(c-'0');
while((c=getchar())>='0'&&c<='9')ret=ret*10+(c-'0');
ret*=sgn;
return true;
}  
inline void put(int x){
if(x< 0){
putchar('-');
x = -x;
}
if(x == 0){
putchar('0');
return;
}
char s[20];
int bas = 0;
for(;x;x/=10)s[bas++] = x%10+'0';
for(;bas--;)putchar(s[bas]);
return;
}

int main(){
scanf("%d%d",&n,&k);
f1=f2=0;
t1=t2=-1;
for(int i=0;i<n;++i){
readint(c[i]);
if(i<k-1){
addmin(c[i],i);
addmax(c[i],i);
}
}
for(int i=k-1;i<n-1;++i){
addmin(c[i],i);
put(getmin(i-k+1));
putchar(' ');
}
addmin(c[n-1],n-1);
printf("%d\n",getmin(n-k));
for(int i=k-1;i<n-1;++i){
addmax(c[i],i);
put(getmax(i-k+1));
putchar(' ');
}
addmax(c[n-1],n-1);
printf("%d\n",getmax(n-k));
return 0;
}
  评论这张
 
阅读(1098)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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