程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> POJ 2823 Sliding Window(單調隊列)

POJ 2823 Sliding Window(單調隊列)

編輯：關於C++

單調隊列典型題

An array of size n ≤ 10 ⁶ is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example:
The array is [1 3 -1 -3 5 3 6 7], and k is 3.

Window position Minimum value Maximum value [1 3 -1] -3 5 3 6 7 -1 3 1 [3 -1 -3] 5 3 6 7 -3 3 1 3 [-1 -3 5] 3 6 7 -3 5 1 3 -1 [-3 5 3] 6 7 -3 5 1 3 -1 -3 [5 3 6] 7 3 6 1 3 -1 -3 5 [3 6 7] 3 7

Your task is to determine the maximum and minimum values in the sliding window at each position.

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include 
#include
#include 
#include
#define eps 1e-6 
#define LL long long  
using namespace std;  

const int maxn = 2000000;
//const int INF = 0x3f3f3f3f;
int n, k;
int a[maxn];
//單調隊列
int qmin[maxn], vmin[maxn], hmin = 1, tmin = 0; 
void Min(int a, int i) {  //第i個元素a入隊 
	while(hmin<=tmin && vmin[hmin] <= i-k) hmin++;  //超范圍隊首出隊 
	//while(hmin<=tmin && qmin[tmin]>=a) tmin--; //不符合要求隊尾出列 
	int l = hmin, r = tmin;
	while(l <= r) {
		int m = l+(r-l)/2;
		if(qmin[m] >= a) r = m - 1;
		else l = m + 1; 
	}
	tmin = ++r;
	qmin[tmin] = a;
	vmin[tmin] = i;
}
int qmax[maxn], vmax[maxn], hmax = 1, tmax = 0; 
void Max(int a, int i) {  //第i個元素a入隊 
	while(hmax<=tmax && vmax[hmax] <= i-k) hmax++;  //超范圍隊首出隊 
	//while(hmax<=tmax && qmax[tmax]<=a) tmax--; //不符合要求隊尾出列 
	int l = hmax, r = tmax;
	while(l <= r) {
		int m = l+(r-l)/2;
		if(qmax[m] <= a) r = m - 1;
		else l = m + 1; 
	}
	tmax = ++r;
	qmax[tmax] = a;
	vmax[tmax] = i;
}
int ansMax[maxn], ansMin[maxn];
int main() {
//	freopen(input.txt, r, stdin);
	while(scanf(%d%d, &n, &k) == 2) {
		hmin = 1, tmin = 0;
		hmax = 1, tmax = 0;
		for(int i = 1; i <= n; i++) scanf(%d, &a[i]);
		for(int i = 1; i < k; i++) {
			Min(a[i], i);
			Max(a[i], i);
		}
		for(int i = k; i <= n; i++) {
			Min(a[i], i);
			ansMin[i-k] = qmin[hmin];
			Max(a[i], i);
			ansMax[i-k] = qmax[hmax];
		}
		for(int i = 0; i <= n-k; i++) 
			if(i != n-k) printf(%d , ansMin[i]);
			else printf(%d
, ansMin[i]);
		for(int i = 0; i <= n-k; i++) 
			if(i != n-k) printf(%d , ansMax[i]);
			else printf(%d
, ansMax[i]);
	}
	return 0;
}