以下是我的程序:
#include<cstdio>
#define maxn 1048600
#define none 2000000000

int D[maxn],V[maxn],N,upd,ans=0,nn=0;
void solve(int);
int find(int);
int main(){

  scanf("%d",&N); 
  int i,k,r; nn=1;
  for (i=1;i<=N;i++) nn*=2;
  N=0; --nn;
  while (1){
	if (scanf("%d",&r)==EOF) break;
	if (N+1>nn) break;
	D[++N]=r;
  }
  nn=0; upd=0; solve(1); D[0]=-none;
  for (i=1;i<=N+1;i++) D[i]=none;
  for (i=1;i<=N;i++){
	k=find(V[i]);
	D[k]=V[i];
	if (k>ans) ans=k;
  }
  printf("%d\n",N-ans);
}
void solve(int r){
  if (r>N) return;
  solve(r*2);
  solve(r*2+1);
  V[++nn]=D[r]-upd;
  if (r%2==0) ++upd;
}
int find(int p){
  int l=0,m=N+1,r=(l+m)/2,x=N*2;
  while (l<=m){
	if (D[r]<=p) l=r+1; else { if (r<x) x=r; m=r-1; }
	r=(l+m)/2;
  }
  return x;
}

• Re:pku3214总是wa.那位大牛能给我程序?谢谢! (871) smcdfeng 2007-12-11 21:46:41