磁盘文件最优存储问题

佚名 6年前 (2019-04-27) 随笔 1618人围观抢沙发百度已收录

/* 贪心书法——磁盘文件最优存储问题
   将概率最大的放在中间，依次左右两边排较小的
   2019-04-27
*/
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std ;
int cmp(int a, int b)
{
	return (a > b);
}

/*将数组a的值排序使其元素的分布从中间往两边依次减少*/
void strageSort(int n, int a[]) 
{
	int i, k, mid;
	sort(a, a + n, cmp);
	mid = n / 2;
	int * b = (int *)malloc(sizeof(int) * (n+1));  // 分配存储空间
	b[mid] = a[0]; // 将最大数放在中间
	for (i = 1, k = 1; i< n; i++, k++)
	{   //数组a的值分布从中间往两边依次减少
		b[mid - k] = a[i];
		i++;
		if (i != n)
			b[mid + k] = a[i];
	}
	for (int i = 0; i<n; i++) 
	{        //经变化后的a数组
		a[i] = b[i];
	}
}

/*计算排序之后检索n个文件的期望时间*/
double  minStorage(int n, int a[]) 
{
	int sum = 0;
	for (int i = 0; i<n; i++) {
		sum += a[i];
	}
	double result = 0;
	for (int i = 0; i<n; i++) {
		for (int j = i + 1; j<n; j++) {    //从磁道0-n-1。计算它们的磁道间的检索时间
			result += (a[i] * 1.0 / sum)*(a[j] * 1.0 / sum)*(j - i);
		}
	}
	return result;
}


int main()
{
	freopen("in.txt","r",stdin);
	freopen("out.txt", "w", stdout);
	int N; // 输入文件个数
	cin >> N; // 

	int * Pro = (int *)malloc(sizeof(int) * N);  // 分配存储空间
	for (int i = 0; i < N; i++)
	{
		cin >> Pro[i];
	}
	strageSort(N, Pro);
	double res = minStorage(N, Pro);
	cout << res;
	fclose(stdin);
	fclose(stdout);
	return 0;
}