aflow.cpp

用贪心算法解决aflow 有调整时间的流水作业调度问题。

#include<iostream.h>
#include<fstream.h>
#include<math.h>

template <class T>
void Swap(T &a,T &b)
{
	T temp = a;
	a = b;
	b = temp;
}

//template <class T>
int Partition(double a[], int p, int r, int b[], int c[])
{
	int i=p,j=r+1;
	double x = a[p];
	int temp_b = b[p];
	int temp_c = c[p];
	while(true){
		while(a[++i]>x&&i<=j);     //空语句
		while(a[--j]<x&&j>=i);     //空语句
		if(i>=j) break;
		Swap(a[i],a[j]);
		Swap(b[i],b[j]);
		Swap(c[i],c[j]);
	}
	a[p] = a[j];
	a[j] = x;
	b[p] = b[j];
	b[j] = temp_b;
	c[p] = c[j];
	c[j] = temp_c;
	return j;
}

//template <class T>
void QuickSort(double a[], int p, int r, int b[], int c[])
{
	if(p<r){
		int q = Partition(a, p, r, b, c);
		QuickSort(a, p, q-1, b, c);
		QuickSort(a, q+1, r, b, c);
	}
}

int main()
{
	ifstream in("input.txt");
	ofstream out("output.txt");
	int n;
	in>>n;
	int *s1 = new int[n];
	int *t1 = new int[n];
	int *s2 = new int[n];
	int *t2 = new int[n];
	int *w  = new int[n];
	int *Time = new int[n];
	double *weight = new double[n];
	for(int i=0; i<n; i++)
	{
		in>>s1[i];
		in>>t1[i];
		in>>s2[i];
		in>>t2[i];
		in>>w[i];
		Time[i] = s2[i] + t2[i];
		weight[i] = double(w[i]) / double(s2[i] + t2[i]);
	}
	QuickSort(weight, 0, n-1, Time, w);
	/*for(int j=0; j<n; j++)
	{
		cout<<Time[j]<<" ";
	}*/
	int *FinishTime = new int[n];
	FinishTime[0] = Time[0];
	//计算每个作业的完成时间
	for(int j=1; j<n; j++)
	{
		FinishTime[j] = FinishTime[j-1] + Time[j];
	}
	int sum = 0;
	for(j=0; j<n; j++)
	{
		sum += FinishTime[j] * w[j];
	}
	out<<sum<<endl;

	delete []s1;
	delete []t1;
	delete []s2;
	delete []t2;
	delete []w;
	delete []Time;
	delete []weight;
	delete []FinishTime;
	return 0;
}