贪心算法---Disk file optimal storage

问题描述：

设磁盘上有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