比赛 至少完成十道练习 评测结果 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();