waits.cpp

设计一个算法

#include<iostream>
#include<fstream>
using namespace std;
template<class T>
class MinHeap
{
	public:
		MinHeap(int MinHeapSize);
		~MinHeap(){delete[]heap;}
		int Size()const{return Last;}
		T Min(){return heap[1];}
		MinHeap<T>&Insert(const T&x);
        MinHeap<T>&DeleteMin(T&x);
		void Initialize(T a[],int size,int ArraySize);
		void Deactivate(){heap=0;}
	private:
		int Last,MaxSize;
		T *heap;
};
template<class T>
MinHeap<T>::MinHeap(int MinHeapSize)
{
	MaxSize=MinHeapSize;
	heap=new T[MaxSize+1];
	Last=0;
}
template<class T>
MinHeap<T>&MinHeap<T>::Insert(const T&x)
{
	int i=++Last;
	while(i!=1&&x<heap[i/2])
	{
		heap[i]=heap[i/2];
		i/=2;
	}
	heap[i]=x;
	return *this;
}
template<class T>
MinHeap<T>&MinHeap<T>::DeleteMin(T&x)
{
	x=heap[1];
	T y=heap[Last--];
	int i=1,ci=2;
	while(ci<=Last)
	{
		if(ci<Last&&heap[ci]>heap[ci+1]) ci++;
		if(y<=heap[ci]) break;
		heap[i]=heap[ci];
		i=ci;
		ci*=2;
	}
	heap[i]=y;
	return *this;
}
template<class T>
void MinHeap<T>::Initialize(T a[],int size,int ArraySize)
{
	delete[]heap;
	heap=a;
	Last=size;
	MaxSize=ArraySize;
	for(int i=Last/2;i>=1;i--)
	{
		T y=heap[i];
		int c=2*i;
		while(c<=Last)
		{
			if(c<Last&&heap[c]>heap[c+1]) c++;
			if(y<=heap[c]) break;
			heap[c/2]=heap[c];
			c*=2;
		}
		heap[c/2]=y;
	}
}
template<class T>
void HeapSort(T a[],int n)
{
	MinHeap<T> H(1);
	H.Initialize(a,n,n);
	T x;
	for(int i=n-1;i>=1;i--)
	{
		H.DeleteMin(x);
		a[i+1]=x;
	}
	H.Deactivate();
}
int main()
{
    ifstream in("c:\\input.txt");
    ofstream out("c:\\output.txt");
    if(!in.is_open())
	{
        out<<"error"<<endl;
        exit(1);
    }
	int n,s;
	double sum=0;
	in>>n>>s;
	int *a=new int[n+1];
    for(int i=1;i<=n;i++)
        in>>a[i];
    HeapSort(a,n);
	for(i=n;i-s>=1;i--)
		a[i-s]+=a[i];
	for(i=1;i<=n;i++)
		sum+=a[i];
	out<<sum/n<<endl;
	delete[]a;
    in.close();
    out.close();
    return 0;
}