问题描述：
设磁盘上有n个文件，f1,f2,…,fn，，每个文件占磁盘上1个磁道。这n个文件的检索概率分别是p1,p2,…,pn,且p1+p2+…+pn =1。磁头从当前磁道移到被检信息磁道所需的时间可用这2个磁道之间的径向距离来度量。如果文件pi存放在第i道上,1<i<n ，则检索这n 个文件的期望时间是 ∑【PiPjd（i，j）】 ,其中 d（i，j）是第i道与第j 道之间的径向距离| i - j |。
要求：
输入：第1行是正整数n,表示文件个数。第2行有n个正整数ai，表示文件的检索概率。
输出：计算出的最小期望检索时间。
思路：
先将n个文件按访问概率从大到小排序，概率最大的应该放中间，次大的和次次大的放最大的两边，再小一点的再放在次大的左边和次次大的右边
具体算法：
将文件按概率排序后，用一个新的数组代表各文件存放位置，先确定mid值，再依次确定mid两边，mid两边的两边的各文件，不断的循环，最后各文件就再新的数组里放好了位置
举例：
5 个文件
检索概率分别为：[9 11 22 33 55]
将检索概率经过strageSort函数变化为 [11 33 55 22 9]
最后调用minStore函数计算概率即可
#include <iostream>
#include <algorithm>
using namespace std;
bool cmp(int a,int b)
{
return a > b;
}
void strageSort(int n,int a[]) //将数组a的值排序使其元素的分布从中间往两边依次减少
{
int i,k,mid;
sort(a,a+n,cmp) ; //将数组元素降序排序
mid = n/2; //取中间元素位置
int b[n+1]; //定义一个长度为n+1的数组b
b[mid] = a[0]; //将最大元素的放在b数组的中间位置
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];
}
}
void minStore(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++){
result += (a[i]*1.0/sum)*(a[j]*1.0/sum)*(j-i);//计算最小期望检索时间
}
}
cout << "最小期望检索时间：" << result <<endl; //输出
}
int main()
{
int n,k,mid,i;
cout << "输入文件的个数：" << endl;
cin >> n;
int a[n+1] ;
cout << "输入文件的检索概率：" << endl;
for(int i = 0; i < n; i++)
{
cin >> a[i];
}
strageSort(n,a);
minStore(n,a);
return 0;
}
//test:
输入文件的个数：
5
输入文件的检索概率：
9 11 22 33 55
最小期望检索时间：0.547396
关于c++ Sort函数的使用，参考链接：
https://blog.csdn.net/w_linux/article/details/76222112
