The nearest taller cow - nazgul's Blog

The nearest taller cow

nazgul posted @ 2010年10月18日 23:43 in HNU , 1001 阅读

http://acm.hnu.cn/online/?action=problem&type=show&id=11449

用一个栈进行扫描，维护栈内元素的单调性

分别求出每个元素左边和右边的最近的更高元素，再取最大值，最后再求和取均值。

以求左边的为例，先从左往右扫描，遇到小于等于栈顶元素的数就将这个数入栈，继续向后扫；如果大于则弹出栈顶元素，并设置其左边最近元素为此新元素。

	#include <stdio.h>
#include <string.h>
#define NIL 0x01010101

int a[1000001], f[1000001];
int q[1000001], l;

int main()
{
	int n, t, i, j, imax ;
	double tt;
	//freopen( "//home//administrator//2.in", "r", stdin );
	scanf( "%d", &t );
	while ( scanf( "%d", &n ) != EOF )
	{
		memset( f, 1, sizeof( f ) );
		for ( imax=i=0; i<n; i++ )
		{
			scanf( "%d", &a[i] );
			if ( imax < a[i] ) imax = a[i];
		}
		l = -1;
		for ( i=0; i<n; ++i )
		{
			while ( l >= 0 && a[i] >= a[q[l]] )
			{
				/×如果当前值等于栈中元素，则它最近距离为它到与它相等的距离+那个相等的数的最近距离×/
				if ( a[i] == a[q[l]] )
				{
					f[i] = f[q[l]]+i-q[l];
					break;
				}
				/×如果最短距离可以更新*/
				if ( f[q[l]] > i-q[l] )
					f[q[l]] = i-q[l];
				l--;
			}
			/*找到栈中比a[i]大的数，记录距离*/
			if ( l != -1 && a[i] != a[q[l]] ) f[i] = i-q[l];
			/*入栈*/
			q[++l] = i;
		}
		tt = 0;
		for ( i=0; i<n; ++i )
		{
			if ( a[i] == imax || f[i] == NIL ) f[i] = n;
			tt += f[i];
		}
		/*注意进位*/
		printf( "%.2f\n", ( tt*100+0.5 )/100/n );
	}
	return 0;
}