2823.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Problem Id:2823  User Id:fzk 
#include <stdio.h>
#include <algorithm>
using namespace std;
int a[1000100], l[1000100], ans[1000100];
int pt[1000100], st[1000100], n, k, m;
bool cmp( int x, int y ) {
	return a[x] < a[y];
}
void calc( ) {
	int i, j, h, sn;	
	for( i=0; i<n; i++ )
		l[i] = i-1, ans[i] = (1<<31), pt[i] = i;	
	l[0] = -10000000;
	sort( pt, pt+n, cmp );
	for( i=0; i<m; i++ ) {
		h = pt[i];
		st[ 0 ] = h;
		sn = 1;
		for( j=l[h]; j>h-k; j=l[j] )
			st[ sn++ ] = j;
		while( sn-- ) {
			l[ st[sn] ] = j;
			if( ans[ st[sn] ] == (1<<31) )
				ans[ st[sn] ] = a[ h ];
		}
	}
}
int main( ) {
	int i;		
	scanf( "%d%d", &n, &k );
	for( i=0; i<n; i++ )
		scanf( "%d", a+i );	
	m = n-k+1;
	calc( );
	for( i=0; i<m; i++ ) {
		printf( "%d", ans[i] );
		if( i != m-1 )printf( " " );
		else printf( "\n" );
	}
	for( i=0; i<n; i++ )
		a[i] = -a[i];
	calc( );
	for( i=0; i<m; i++ ) {
		printf( "%d", -ans[i] );
		if( i != m-1 )printf( " " );
		else printf( "\n" );
	}
	return 0;
}