ex(最佳调度问题）.cpp

最佳调度问题

#include<fstream.h>
#include<iostream.h>
//#include<time.h>

int tan(int n,int k);
void back(int i,int last);
void QuickSort(int a[],int p,int r);
int Partition(int a[],int p,int r);

const int maxn=100000,maxk=100000;
int t[maxn+1],x[maxn+1],m[maxk+1];
int best,n,k,average;
bool stop=false;

void main()
{
	ifstream in("input.txt");
	ofstream out("output.txt");
	in>>n;
	in>>k;
	for(int i=1;i<=n;i++)
		in>>t[i];
	
	int sum=0;
	for(i=1;i<=n;i++)
		sum+=t[i];
	average=(sum-1)/k+1;
	QuickSort(t,1,n);
	int temp;
	for(i=1;i<=n/2;i++)
	{
		temp=t[i];
		t[i]=t[n-i+1];
		t[n-i+1]=temp;
	}
	best=tan(n,k);
	for(i=1;i<=k;i++)
		m[i]=0;
	back(1,1);
	out<<best;
}

void back(int i,int last)
{
	if(i>n)
	{
		best=m[last];
		if(best==average)
			stop=true;
	}
	else
	{
		int temp;
			for(int num=1;num<=k;num++)
			{
				{
				if( (num>1)&&(m[num-1]==m[num]) )
					continue;
				if( (num>2)&&(m[num-2]==m[num]) )
					continue;
				}
				x[i]=num;
				m[num]+=t[i];
				temp=m[num]>m[last]?num:last;
				if(m[temp]<best)
					back(i+1,temp);
				if(stop)
					return;
				m[num]-=t[i];
				if(m[num]==0)
					return;
			}
	}
}

int tan(int n,int k)
{
	for(int i=1;i<=k;i++)
		m[i]=0;
	int label=1;
	for(i=1;i<=n;i++)
	{
		m[label]+=t[i];
		for(int j=1;j<=k;j++)
			if(m[j]<m[label])
				label=j;
	}
	int result=m[1];
	for(i=2;i<=k;i++)
		if(m[i]>result)
			result=m[i];
	return result;
}

void QuickSort(int a[],int p,int r){
	if (p<r){
		int q=Partition(a,p,r);
		QuickSort(a,p,q-1);
		QuickSort(a,q+1,r);
	}
}

int Partition(int a[],int p,int r){
	int i=p,
	j=r+1;
    int x=a[p],temp;
	while(true){
		while( (i<r)&&(a[++i]<x) );
		while( (j>p)&&(a[--j]>x) );
		if(i>=j) break;
		temp=a[i];
		a[i]=a[j];
		a[j]=temp;
	}
	a[p]=a[j];
	a[j]=x;
	return j;
}