2823slidingwindow.cpp

算法编程题,北京大学OnlineJudge 2823SlidingWindow

#include<stdio.h>  
#include<math.h>
#include<stdlib.h>
#include<memory.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<sstream>
#include<vector>
#include<set>
#include<map>
using namespace std;


//ά

int a[1000000];
int q[1000000];
int n,K;

bool Input(){
	if(scanf("%d%d",&n,&K)==EOF){
		return 0;
	}
	int i;
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	return 1;
}

void Solve(){
	int i,j,k,f,r;
	q[0]=0,f=0,r=0;
	for(i=1;i<K;i++){
		while(r>=0&&a[i]<=a[q[r]]){
			r--;
		}
		q[++r]=i;
	}
	printf("%d",a[q[f]]);
	for(;i<n;i++){
		if(q[f]<i-K+1){
			f++;
		}
		while(r>=f&&a[i]<=a[q[r]]){
			r--;
		}
		q[++r]=i;
		printf(" %d",a[q[f]]);
	}
	printf("\n");

	q[0]=0,f=0,r=0;
	for(i=1;i<K;i++){
		while(r>=0&&a[i]>=a[q[r]]){
			r--;
		}
		q[++r]=i;
	}
	printf("%d",a[q[f]]);
	for(;i<n;i++){
		if(q[f]<i-K+1){
			f++;
		}
		while(r>=f&&a[i]>=a[q[r]]){
			r--;
		}
		q[++r]=i;
		printf(" %d",a[q[f]]);
	}
	printf("\n");

	return;
}

int main()
{
	//freopen("in.txt","r",stdin);
	while(Input()){
		Solve();
	}
	return 0;
}