社区讨论
求大佬解释为什么这个手写的单调双端队列维护不对
P1886【模板】单调队列 / 滑动窗口参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mi6i71qv
- 此快照首次捕获于
- 2025/11/20 05:17 4 个月前
- 此快照最后确认于
- 2025/11/20 05:17 4 个月前
只有10分QAQ
CPP#include <cstdio>
#define MAXN 1000010
int head,tail;
int num[MAXN],val[MAXN];
int n,k,a[MAXN];
int main(){
int t;
scanf("%d%d",&n,&k);
for(int i=0;i<n;++i){
scanf("%d",&a[i]);
}
val[0]=a[0];
++tail;
for(int i=1;i<k;++i){
while(a[i]<num[tail-1]&&head<tail){
--tail;
}
val[tail]=a[i];
num[tail++]=i;
}
printf("%d ",val[head]);
for(int i=k;i<n;++i){
while(a[i]<num[tail-1]&&head<tail){
--tail;
}
val[tail]=a[i];
num[tail++]=i;
if(i-num[head]==k){
++head;
}
printf("%d ",val[head]);
}
//
printf("\n");
//
head=0;
tail=0;
val[0]=a[0];
num[0]=0;
++tail;
for(int i=1;i<k;++i){
while(a[i]>num[tail-1]&&head<tail){
--tail;
}
val[tail]=a[i];
num[tail++]=i;
}
printf("%d ",val[head]);
for(int i=k;i<n;++i){
while(a[i]>num[tail-1]&&head<tail){
--tail;
}
val[tail]=a[i];
num[tail++]=i;
if(i-num[head]==k){
++head;
}
printf("%d ",val[head]);
}
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...