2176971_wa.cc

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

# include <cstdio>
# include <vector>

using namespace std;

int i, n, H, A, x;
vector <int> h;
vector <int> a;
vector <int> dp;
char c;

void run(int m)
{
	if(2*m+1<H) run(2*m+1);
	if(2*(m+1)<H) {x++; run(2*(m+1));}
	a[A++]=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 = 0;
	scanf("%d",&n);
	h.resize(1<<n);
	dp.resize(1<<n);
	while(scanf("%d",&tmp)==1)
	{	
		a.push_back(tmp);
		H++;
	}
	run(0);
	int max=0;
	for(i=1;i<A;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-max);
	return 1;
}