poj2823/hdu3415 - 数据结构 单调队列
2024-08-26 14:51:25
长度为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 ;
}
长度为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 ;
}
最新文章
- 封装的ajax请求
- C#检测本地网络状态
- ubuntu查看系统资源占用(内存,cpu和进程)
- Git详解之三 Git分支
- RMI、RPC、SOAP通讯技术介绍及比对 - XML/SOAP
- XEE介绍
- [转] C# 中的static静态变量
- FANTASY:In which way do you think the world will end?
- vector -1
- You don&#39;t seem to have &#39;make&#39; or &#39;gmake&#39; in your PATH
- mp3播放器
- 怎样用Java编写一段代码引发内存泄露
- HTML基本介绍
- INSTEAD OF触发器
- CAS 之 Hello World(二)
- Swift如何取得View所属的ViewController
- Dubbo基本特性之泛化调用
- Super Mario HDU - 4417 (主席树)
- 第十节:数据批注(DataAnnotationModel)和自定义验证(包括Model级别的验证)
- .net WebApi中使用swagger生成WepApi集成测试工具
热门文章
- VC++基于CXImage库实现缩略图
- VMware虚拟机的CentOS7安装Nginx后本机用CentOS的IP地址无法访问
- 解决django.db.utils.InternalError: (1049, ";Unknown database &#39;exam_db&#39;";)
- jqGrid多级表格的实现
- Creative Cloud&#160;安装出错,错误代码:207
- Java经典逻辑编程50题
- 读 Real-Time Rendering 收获 - chapter 6. texturing
- Html表单提交到Servlet输出到页面乱码
- POJ 1664 放苹果【DFS】
- Git常见问题 资料汇总