pku2823.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 62 行

#include <stdio.h>
#define size 1000001

int v[size];
int q[size];
int head, tail;

int N, K;

int main()
{
	int i;
	while (scanf("%d %d", &N, &K) != -1)
	{
		for (i = 0; i < N; i++)
		{
			scanf("%d", &v[i]);
		}
		head = 0;
		tail = 0;
		q[0] = 0;
		for (i = 0; i < N; i++)
		{
			if (i - q[tail] >= K)
				tail++;
			while (head >= tail && v[q[head]] >= v[i])
			{
				head--;
			}
			head++;
			q[head] = i;
			if (i >= K - 1)
			{
				printf("%d ", v[q[tail]]);
			}
		}
		printf("\n");

		head = 0;
		tail = 0;
		q[0] = 0;
		for (i = 0; i < N; i++)
		{
			if (i - q[tail] >= K)
				tail++;
			while (head >= tail && v[q[head]] <= v[i])
			{
				head--;
			}
			head++;
			q[head] = i;
			if (i >= K - 1)
			{
				printf("%d ", v[q[tail]]);
			}
		}
		printf("\n");
	}
	return 0;
}