3110123_wa.cpp

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

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

using namespace std;

int s(int a[],int m,int p,int q)
{
	int t;
	while(p<=q)
	{
		t=(p+q)/2;
		if(a[t]<=m) p=t+1;
		else
		{
			if(t-1<0||a[t-1]<=m) return t;
			else q=t-1;
		}
	}
	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);
			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 = i-0-n1+n-i-n2;
		if(tmp < ans)
		{
			ans = tmp;
		}
	}
	printf("%d\n",ans);
	return 1;
}