3110745_ac_763ms_172k.cpp

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

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

using namespace std;

int s(int a[],int m,int p,int q)
{
	int i;

	for(i = p; i <= q; i++)
	{
		if(a[i]==m)
			return i;
	}
	for(i = p; i < q; i++)
	{
		if(a[i]<m&&a[i+1]>m)
			return i+1;
	}
	assert(NULL);
	return -1;
}

int f(int a[],int st,int ed)
{
	int i, x, max;

	if(st==ed)
	{
		return 0;
	}
	max=0;
	for(i = 1; i < ed; i++)
	{
		if(a[i] < a[0]) a[0] = a[i];
		else if(a[i]>a[max]) {max++; a[max]=a[i];}
		else 
		{
			x=s(a,a[i],0,max);
			if(x!=-1)a[x]=a[i];
		}
	}
	max++;
	return max;
}

int main()
{
	double h;
	int n, n1, n2, ans, tmp;
	int i, a[1001], b[1001], ta[1001];

	scanf("%d",&n);
	for(i = 0; i < n; i++)
	{
		scanf("%lf",&h);
		h *= 1e5;
		a[i] = (int)h;
	}
	ans = 10000000;
	for(i = 0; i <= n; i++)
	{
		memcpy(ta,a,sizeof(a));
		reverse_copy(a,&a[n],b);
		n1 = f(ta,0,i);	
		n2 = f(b,0,n-i);
		tmp = n-n1-n2;
		if(tmp < ans)
		{
			ans = tmp;
		}
	}
	printf("%d\n",ans);
	return 1;
}