poj2823 题目链接

长度为N的数组,求宽度k的滑动窗口在数组上滑动时窗口内的最大值或最小值

如果用单调队列做,求最小值时,队列应该严格递增的。所以插入时,队尾大于等于插入值的元素都应被舍弃,因为插入元素不仅小而且新,没有必要保留队尾这些又大又旧的元素。

/*
选C++交是5k多毫秒,但是G++就会超时。
*/
#include <cstdio>
#include <cstring>
const int N = ;
int data[N];
int o1[N],o2[N];
int q[N];
int n,k;
void getMin(){
int head,tail;
head = tail = ;
for(int i=;i<n;i++){
while((tail>head)&&data[q[tail-]]>data[i]) tail--;
q[tail++] = i;
if(i>=(k-)){
while((head<tail)&&q[head]<(i-k+)) head++;
o1[i-k+] = data[q[head]];
}
}
}
void getMax(){
int head,tail;
head = tail = ;
for(int i=;i<n;i++){
while((head<tail)&&(data[q[tail-]]<data[i])) tail--;
q[tail++] = i;
if(i>=(k-)){
while((head<tail)&&(q[head]<(i-k+))) head++;
o2[i-k+] = data[q[head]];
}
}
}
int main(){
scanf("%d%d",&n,&k);
for(int i=;i<n;i++) scanf("%d",data+i);
getMin();
getMax();
for(int i=;i<n-k+;i++) printf("%d ",o1[i]); puts("");
for(int i=;i<n-k+;i++) printf("%d ",o2[i]); puts("");
return ;
}

hdu3415 题目链接

长度为N的数组,长度小于等于K的非空子串的最大和。

求完前缀和后就转化成了窗宽为k的单调队列

#include <cstdio>
#include <cstring>
const int N = ;
const int INF = 0x0FFFFFFF;
int data[N],sum[N*];
int q[N*];
int n,k,total;
int minq(int &spos,int &epos){
int head,tail;
head = tail = ;
int ans = -INF;
for(int i=;i<total;i++){
while((head<tail)&&(sum[q[tail-]]>=sum[i-])) tail--;
while((head<tail)&&q[head]<i-k) head++;
q[tail++] = i-;
if((sum[i]-sum[q[head]]>ans)){
spos = q[head];
epos = i;
ans = sum[epos]-sum[spos];
}
}
return ans;
}
int main(){
int t;
for(scanf("%d",&t);t--;){
scanf("%d%d",&n,&k);
sum[] = ;
for(int i=;i<=n;i++){
scanf("%d",data+i);
sum[i]=sum[i-]+data[i];
}
for(int i=;i<k;i++) sum[n+i]=sum[n+i-]+data[i]; total = n+k;
int spos,epos;
int ans = minq(spos,epos);
spos++;
if(epos>n) epos-=n;
if(spos>n) spos-=n;
printf("%d %d %d\n",ans,spos,epos);
}
return ;
}

最新文章

  1. 封装的ajax请求
  2. C#检测本地网络状态
  3. ubuntu查看系统资源占用(内存,cpu和进程)
  4. Git详解之三 Git分支
  5. RMI、RPC、SOAP通讯技术介绍及比对 - XML/SOAP
  6. XEE介绍
  7. [转] C# 中的static静态变量
  8. FANTASY:In which way do you think the world will end?
  9. vector -1
  10. You don&#39;t seem to have &#39;make&#39; or &#39;gmake&#39; in your PATH
  11. mp3播放器
  12. 怎样用Java编写一段代码引发内存泄露
  13. HTML基本介绍
  14. INSTEAD OF触发器
  15. CAS 之 Hello World(二)
  16. Swift如何取得View所属的ViewController
  17. Dubbo基本特性之泛化调用
  18. Super Mario HDU - 4417 (主席树)
  19. 第十节:数据批注(DataAnnotationModel)和自定义验证(包括Model级别的验证)
  20. .net WebApi中使用swagger生成WepApi集成测试工具

热门文章

  1. VC++基于CXImage库实现缩略图
  2. VMware虚拟机的CentOS7安装Nginx后本机用CentOS的IP地址无法访问
  3. 解决django.db.utils.InternalError: (1049, &quot;Unknown database &#39;exam_db&#39;&quot;)
  4. jqGrid多级表格的实现
  5. Creative Cloud&#160;安装出错,错误代码:207
  6. Java经典逻辑编程50题
  7. 读 Real-Time Rendering 收获 - chapter 6. texturing
  8. Html表单提交到Servlet输出到页面乱码
  9. POJ 1664 放苹果【DFS】
  10. Git常见问题 资料汇总