2176977_ac_935ms_8272k.c

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

#include <stdio.h>
int i,n,h[1<<20],a[1<<20],h_size,a_size,x,max;
char c;
void run(int m)
{
	if(2*m+1<h_size) run(2*m+1);
	if(2*(m+1)<h_size) {x++; run(2*(m+1));}
	a[a_size++]=h[m]-x;
}
int s(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 main()
{
	int tmp;

	h_size=x=a_size=0;
	scanf("%d",&n);
	while(scanf("%d",&tmp)==1)
		h[h_size++] = tmp;
	run(0);
	max=0;
	for(i=1;i<a_size;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[i],0,max);
			a[x]=a[i];
		}
	}
	max++;
	printf("%d\n",h_size-max);
	return 1;
}