1836.txt

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

#include <stdio.h>
#include <algorithm>
#include <memory.h>
using namespace std;
const int size = 1010;
int st[size], sn;
int ans1[size], ans2[size];
int h[size];
int main( )
{
	int n, i, *p, ans, t;
	double s;
	scanf( "%d", &n );
	for( i=0; i<n; i++ )
	{
		scanf( "%lf", &s );
		h[i] = int( s*1000000 + 0.5 );
	}
	sn = 0;
	for( i=0; i<n; i++ )
	{
		p = lower_bound( st, st+sn, h[i] );
		*p = h[i];
		if( p == st+sn )
			sn++;

		ans1[i] = sn;
	}
	sn = 0;
	for( i=n-1; i>=0; i-- )
	{
		p = lower_bound( st, st+sn, h[i] );
		*p = h[i];
		if( p == st+sn )
			sn++;

		ans2[i] = sn;
	}
	ans = ans1[n-1];
	if( ans < ans2[0] ) ans = ans2[0];
	for( i=0; i<n-1; i++ )
		if( ( t = ans1[i] + ans2[i+1] ) > ans )
			ans = t;
	printf( "%d\n", n - ans );	
	return 0;
}