2746133_ac_5278ms_18700k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <algorithm>

using namespace std;

int n, k;
int num[1000001];
int max_heap[1000001];
int min_heap[1000001];
int max[1000001], min[1000001];

bool cmp1(int a,int b)
{
	return num[a] < num[b];
}

bool cmp2(int a,int b)
{
	return num[a] > num[b];
}

int main()
{
	int i, r1, r2;
	int n1, n2;

	scanf("%d%d",&n,&k);
	for(i = 0; i < k; i++)
	{
		scanf("%d",&num[i]);
		max_heap[i] = min_heap[i] = i;
	}
	make_heap(max_heap,max_heap+k,cmp1);
	make_heap(min_heap,min_heap+k,cmp2);
	r1 = r2 = k;n1 = n2 = 1;
	max[0] = max_heap[0];min[0] = min_heap[0];
	for(i = k; i < n; i++)
	{
		scanf("%d",&num[i]);
		max_heap[r1++] = i;
		push_heap(max_heap,max_heap+r1,cmp1);
		while(max_heap[0]<=i-k)
			pop_heap(max_heap,max_heap+r1--,cmp1);
		max[n1++] = max_heap[0];
		min_heap[r2++] = i;
		push_heap(min_heap,min_heap+r2,cmp2);
		while(min_heap[0]<=i-k)
			pop_heap(min_heap,min_heap+r2--,cmp2);
		min[n2++] = min_heap[0];
	}
	for(i = 0; i < n2; i++)
		printf("%d ",num[min[i]]);
	printf("\n");
	for(i = 0; i < n1; i++)
		printf("%d ",num[max[i]]);
	printf("\n");
	return 0;
}