tape.cpp

程序最优存储问题 &laquo 问题描述： 设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是i l

#include<fstream.h>
ifstream fin("input.txt");
ofstream fout("output.txt");
//============================
//选择排序
//============================
template< class T >
int Max( T a[], int n )
{//确定a[0:n-1]中最大元素下标
	int pos = 0;
	for( int i=1; i<n; i++ )
		if( a[pos] <a[i] )
			pos = i;
		return pos;
}//--------------------------------------------
template< class T >
void SelectionSort( T a[], int n)
{
	for( int size=n; size>1; size-- )
	{
		int j = Max( a, size );
		Swap( a[j], a[size-1]);
	}
}//------------------------------
//===================================
template< class T >
inline void Swap( T&a, T&b )
{//交换a与b的值
	T temp = a;
	a = b;
	b = temp;
}//-------------------------------------------------
//===========================================
//主函数
//=========================================
void main()
{
	int n;
	fin>>n;
	int *a1 = new int[n];//定义长度的动态数组
	int *a2 = new int[n];//定义读取的概率的动态数组
	float *p = new float[n];//定义实际的概率的动态数组
	float *t = new float[n];//定义长度l与概率p的动态数组
	float *T = new float[n];//定义读取每个程序的时间的动态数组
	int sum = 0;
	float atime = 0;
	for( int i=0; i<n; i++ )
	{
		fin>>a1[i]>>a2[i];
		sum = sum + a2[i];
	}
	for( i=0; i<n; i++ )
		p[i] = (float)a2[i]/sum;
	for( i=0; i<n; i++ )
		t[i] = a1[i]*p[i];
	SelectionSort( t, n );
	for( i=0; i<n; i++ )
		T[i] = 0;
	for( int r=0; r<n; r++ )
	{
		for( i=0; i<=r; i++ )
			T[r] = T[r] + t[i];
	}
	for( r=0; r<n; r++ )
		atime = atime + T[r];
	fout<<atime;
	delete[]a1;
	delete[]a2;
	delete[]p;
	delete[]t;
	delete[]T;
}