Moyyer_suiy @ 2022-10-11 19:26:37
#include<bits/stdc++.h>
const int N = 1000010;
using namespace std;
int n, k, a;
struct s{
int v, num;
};
deque <s> q1, q2;
int ans1[N], ans2[N];
int main(){
cin>> n>> k;
s q;
for(int i = 1; i <= n; i ++){
cin>> a;
q.v = a;
q.num = i;
while(!q1.empty() && a <= q1.back().v) q1.pop_back();
q1.push_back(q);
if(q1.front().num + k <= i) q1.pop_front();
while(!q2.empty() && a >= q2.back().v) q2.pop_back();
q2.push_back(q);
if(q2.front().num + k <= i) q2.pop_front();
if(i >= k){
ans1[i - k + 1] = q1.front().v;
ans2[i - k + 1] = q2.front().v;
}
}
for(int i = 1; i <= n - k + 1; i ++) cout<< ans1[i]<<" ";
cout<< endl;
for(int i = 1; i <= n - k + 1; i ++) cout<< ans2[i]<<" ";
return 0;
}
用双端队列做的,写着写着有点不太理解,为什么21和22行,以及25和26行不能换一下前后顺序,即为什么不可以先把滑出窗口的弹出去然后再将新元素压进来呢?
上面贴的这个代码是对的,然后换一下顺序就不对了,脑子有点绕不过弯不是特别能理解,来求大佬解释一下谢谢!
by Error_Eric @ 2022-10-11 19:33:34
若交换顺序有可能把队列 pop 成空的,此时 q1.front()
会报错。如果先 push 就不能出现这种情况因为刚加进去的不会被 pop 掉。
如果交换兴许改成 (!q1.empty())&&(q1.front().num + k <= i)
就可以了。
这个小细节在你以后的 OI 生涯中大概率会多次遇到。
by Error_Eric @ 2022-10-11 19:33:56
@茉小窈儿
by DeusExMachina @ 2022-10-11 19:34:11
@茉小窈儿 有没有一种可能,pop 着 pop 着连 front 都没有了
by Moyyer_suiy @ 2022-10-12 16:59:23
@Error_Eric 好的谢谢!改后就可以了