好多机调度511slpt.cpp

设计一个算法

#include<iostream.h>
#include<fstream.h>
ofstream out("output.txt");
int M;
template<class t>
class minheap{
	public:
		minheap(int minheapsize=M);
		~minheap(){delete[]heap;}
		int size()const{return last;}
		t min(){if(last==0)exit(1);
		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)
{
	if(last==maxsize)throw;
	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)
{
	if(last==0)throw;
	x=heap[1];
	t y=heap[last--];
	int i=1;
	int 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 MergeSort(T a[],int n)
{T*b=new T[n];
int s=1;
while(s<n){
    MergeSort(a,b,s,n);
    s+=s;
    MergeSort(b,a,s,n);
    s+=s;
      }
}
template<class T>
void Merge(T c[],T d[],int l,int m,int r)
{
int i=l,j=m+1,k=l;
while(i<=m&&j<=r)
if(c[i]<=c[j]) d[k++]=c[i++];
else d[k++]=c[j++];
if(i>m) for(int q=j;q<=r;q++)
           d[k++]=c[q];
else for(int q=i;q<=m;q++)
         d[k++]=c[q];
}
template<class T>
void MergeSort(T x[],T y[],int s,int n)
{int i=0;
while(i<=n-2*s){
Merge(x,y,i,i+s-1,i+2*s-1);
i=i+2*s;}
if(i+s<n) Merge(x,y,i,i+s-1,n-1);
else for(int j=i;j<=n-1;j++)
     y[j]=x[j];
}///////////////////////////////////////////////////////////////////////
void main()
{
	ifstream in("input.txt");
	if(in.fail())
	{
		cout<<"the input.txt is not exist!";
	 
	}
	int n,m;
	in>>n>>m;
	M=m;
	int *a,*b;
	a=new int[n];
	b=new int[n];
	for(int i=0;i<n;i++)
		in>>a[i];
	MergeSort(a,n);
	for(int pp=0;pp<n;pp++)
		b[pp]=a[n-pp-1];
	if(n>m)
	{minheap<int> d(m);
	for(int j=0;j<m;j++)
	   d.insert(b[j]);
	  int p;
	  for(int ii=m;ii<n;ii++)
	  {
		   d.deletemin(p);
		  p=p+b[ii];
		  d.insert(p);
	  }
	 for(int iii=0;iii<m;iii++)
		  d.deletemin(p);
	 out<<p;}
	else
		out<<b[0];
}