比赛 |
至少完成十道练习 |
评测结果 |
AAAAAAAAA |
题目名称 |
滑动窗口 |
最终得分 |
100 |
用户昵称 |
TARDIS |
运行时间 |
0.685 s |
代码语言 |
C++ |
内存使用 |
3.73 MiB |
提交时间 |
2017-05-23 11:14:30 |
显示代码纯文本
#include<bits/stdc++.h>
#define COGS
using namespace std;
const int maxn=1000010;
deque<int> Min;
deque<int> Max;
vector<int> ans1;
vector<int> ans2;
int n,m,k,cnt,temp,ch[maxn];
inline void dealmin(int temp){
int num=Min.size();
if (num==0) {Min.push_back(temp);return;}
while (!Min.empty()&&ch[Min.back()]>ch[temp]) Min.pop_back();
Min.push_back(temp);
if(!Min.empty()&&Min.front()<temp-k+1)Min.pop_front();
}
inline void dealmax(int temp){
int num=Max.size();
if (num==0) {Max.push_back(temp);return;}
while (!Max.empty()&&ch[Max.back()]<ch[temp]) Max.pop_back();
Max.push_back(temp);
if(!Max.empty()&&Max.front()<temp-k+1) Max.pop_front();
}
inline void PRINT(vector <int> t,int num){
for (int i=0;i<num;i++){
printf("%d ",t[i]);
}
printf("\n");
}
int Main(){
//freopen("a.txt","r",stdin);
#ifdef COGS
freopen("window.in","r",stdin);
freopen("window.out","w",stdout);
#endif
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i++){
scanf("%d",&ch[i]);
dealmin(i);
dealmax(i);
if ((++cnt)>=k){
ans1.push_back(ch[Min.front()]);
ans2.push_back(ch[Max.front()]);
}
}
PRINT(ans1,ans1.size());
PRINT(ans2,ans2.size());
return 0;
}
int main(){;}
int xlm=Main();