# include <stdio.h>  

const int MaxSize=11;  
const int ANF=1000000000;
const int INF=-1; 
typedef int ElementType; 
struct HeapStruct 
{ 
int Capacity; 
int Size; 
ElementType Elements[MaxSize]; 
HeapStruct(){ 
  Size=0;  
} 
}H,L; 

void MakeEmpty() 
{ 
H.Size = 0; 
} 
void Insert(ElementType X) 
{ 
if(H.Size>H.Capacity) return; 
int i;
for( i = ++H.Size; H.Elements[ i / 2 ] > X; i /= 2 ) 
  H.Elements[ i ] = H.Elements[ i / 2 ]; 
H.Elements[ i ] = X; 
} 
ElementType DeleteMin() 
{ 
int i, Child; 
ElementType MinElement, LastElement; 
MinElement = H.Elements[ 1 ]; 
LastElement = H.Elements[ H.Size-- ]; 

for( i = 1; i * 2 <= H.Size; i = Child ) 
{ 
  Child = i * 2; 
  if(  Child != H.Size && H.Elements[ Child + 1 ]< H.Elements[ Child ] ) 
   Child++; 
  if( LastElement > H.Elements[ Child ] ) 
   H.Elements[ i ] = H.Elements[ Child ]; 
  else 
   break; 
} 
H.Elements[ i ] = LastElement; 
return MinElement; 
} 

ElementType FindMin(){
	return H.Elements[1];
}
int IsEmpty() 
{ 
return H.Size == 0; 
} 
/////////////////////////////
void MakeEmpty2() 
{ 
	L.Size = 0; 
} 
void Insert2(ElementType X) 
{ 
	if(L.Size>L.Capacity) return; 
	int i; 
	for( i = ++L.Size; L.Elements[ i / 2 ] < X; i /= 2 ) 
		L.Elements[ i ] = L.Elements[ i / 2 ]; 
	L.Elements[ i ] = X; 
} 
ElementType DeleteMin2() 
{ 
	int i, Child; 
	ElementType MinElement, LastElement; 
	MinElement = L.Elements[ 1 ]; 
	LastElement = L.Elements[ L.Size-- ]; 
	
	for( i = 1; i * 2 <= H.Size; i = Child ) 
	{ 
		Child = i * 2; 
		if(  Child != L.Size && L.Elements[ Child + 1 ]> L.Elements[ Child ] ) 
			Child++; 
		if( LastElement < L.Elements[ Child ] ) 
			L.Elements[ i ] = L.Elements[ Child ]; 
		else 
			break; 
	} 
	L.Elements[ i ] = LastElement; 
	return MinElement; 
}

ElementType FindMin2(){
	return L.Elements[1];
}
 
int IsEmpty2() 
{ 
	return L.Size == 0; 
} 

int main(){
	long double sum,sd;
    H.Elements[0]=INF;
	L.Elements[0]=ANF;
    int i,k,n1,n2,n;
	while(scanf("%d %d %d",&n1,&n2,&n),n1){
		sum=sd=0;
    H.Capacity = n1; 
	L.Capacity = n2;
	for(i=0;i<n;i++){
		scanf("%d",&k);
		sum+=k;
		if(H.Capacity>H.Size){
			Insert(k);
		}else{
			if(k>FindMin()){
            DeleteMin();
			Insert(k);
			}
		}
		if(L.Capacity>L.Size){
			Insert2(k);
		}else{
			if(k<FindMin2()){
            DeleteMin2();
			Insert2(k);
			}
		}
	}
	while(!IsEmpty()){
		sd+=DeleteMin();
	}
	while(!IsEmpty2()){
		sd+=DeleteMin2();
	}
	sum-=sd;
	sum/=(long double)n-n1-n2;
	printf("%.6f\n",sum);
	}
	return 1;
} 
 

• Re:有什么数据WA阿，求高手指点。 (25) gzw_02 2008-07-15 15:56:16