社区讨论
为什么都是STLdeque,我却TLE了两个点,蒟蒻求救
P1886【模板】单调队列 / 滑动窗口参与者 12已保存回复 27
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 27 条
- 当前快照
- 1 份
- 快照标识符
- @mi7yuuo1
- 此快照首次捕获于
- 2025/11/21 05:51 4 个月前
- 此快照最后确认于
- 2025/11/21 06:52 4 个月前
C
#include<bits/stdc++.h>
#define N 2000001
using namespace std;
deque <int> dq;
deque <int> dq2;
int a[N],k,d[N],top;
void tj2(int x)
{
while(!dq2.empty()&&a[dq2.back()]>a[x])
{
dq2.pop_back();
}
while(!dq2.empty()&&x-dq2.front()>=k)
{
dq2.pop_front();
}
dq2.push_back(x);
}
void tj(int x)
{
while(!dq.empty()&&a[dq.back()]<a[x])
{
dq.pop_back();
}
while(!dq.empty()&&x-dq.front()>=k)
{
dq.pop_front();
}
dq.push_back(x);
}
int main()
{
int n;
cin>>n>>k;
for(int i=0;i<n;i++)
{
cin>>a[i];
tj(i);
tj2(i);
if(i>=k-1)
{
cout<<a[dq2.front()]<<" ";
d[top++]=a[dq.front()];
}
}
cout<<endl;
for(int i=0;i<top;i++)
cout<<d[i]<<" ";
return 0;
}
回复
共 27 条回复,欢迎继续交流。
正在加载回复...