Suspicious_spy @ 2024-04-15 17:45:23
#include<iostream>
#include<deque>
#define swift ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
deque<int> que_max;
deque<int> que_min;
int a[1000005], res_min[1000005], res_max[1000005];
void POP(deque<int> & que, int val){
if(!que.empty() && val == que.front())
que.pop_front();
}
void push_min(deque<int> & que, int val){
while(!que.empty() && val < que.back())
que.pop_back();
que.push_back(val);
}
void push_max(deque<int> & que, int val){
while(!que.empty() && val > que.back())
que.pop_back();
que.push_back(val);
}
int result(deque<int> que){
return que.front();
}
int main(){
swift
int count_min = 1, count_max = 1;
int n, k;
cin>>n>>k;
for(int i = 1;i <= n;++i){
cin>>a[i];
push_min(que_min, a[i]);
push_max(que_max, a[i]);
if(i > k){
POP(que_min, a[i - k]);
POP(que_max, a[i - k]);
}
if(i >= k){
res_min[count_min++] = result(que_min);
res_max[count_max++] = result(que_max);
}
}
for(int i = 1;i < count_min;++i)
cout<<res_min[i]<<' ';
cout<<endl;
for(int i = 1;i < count_max;++i)
cout<<res_max[i]<<' ';
cout<<endl;
return 0;
}
by kevinZ99 @ 2024-04-15 18:07:07
@Suspicious_spy
最好别用 deque
,这玩意效率非常快。快到你无法想象。
by wbhqm @ 2024-04-23 21:51:56
@Suspicious_spy 超出范围有点多了,应该是思路的问题
by Suspicious_spy @ 2024-04-24 16:45:03
@wbhqm 思路没问题吧,我把deque换成数组后过了, 提交记录: P1886 滑动窗口
by wbhqm @ 2024-04-28 21:15:55
@Suspicious_spy deque速度慢到超出想象,但正确的思路deque是可以a的