郁闷了3天，终于把这算法写出来了，回过头在看着算法，其实十分简单，书上的代码也是，仔细看看，那些乱七八糟的代码挺容易理解的。小弟初学算法，c++也是半桶水，欢迎高手大虾不吝赐教。

贪心算法解决磁盘最优存储问题

问题描述：

设磁盘上有n个文件，f1,f2,…,fn，，每个文件占磁盘上1个磁道。这n个文件的检索概率分别是p1,p2,…,pn,且p1+p2+…+pn   =1。磁头从当前磁道移到被检信息磁道所需的时间可用这2   个磁道之间的径向距离来度量。如果文件pi存放在第i道上,   ，则检索这n   个文件的期望时间是，sum(　pi*pj*d(i,j)　),其中1<=i<j<=n ，d(I,j)是第i道与第j道之间的径向距离|i-j|。 

思路：

如何确定这n   个文件在磁盘上的存储位置，使期望检索时间达到最小。设计一个解此问题的算法，并分析算法的正确性与计算复杂性。

如果对任何i，j，当i<>j时，pi<>pj，则n个文件在磁盘上将有N!种不同的存储方式。如果考虑到f1，f2……fn，这种排列方式与fn……f1排列的期望检索时间相等，则要计算n!/2种不同的盘列方式。

对于指定的i和j，pi和pj是不变的，可变因子是d(i,j),如果将d(i,j)视为一个元素恒定的集合，则他们与排列顺序无关。

采用谈心算法将文件f1放到中心磁道上，f2，f3分别靠着f1的左右磁道，f4在f2右边……应该是最佳方案。

简单C++算法代码：时间复杂度为nlogn

void GreedySearch(int n,double* p,int& x)

{//p为概率，x作为文件排列结果

       int k[];

       int r,l;

       将p[]按非递增序列排列p[k[1]]>=p[k[2]]……>=p[k[n]];

// 这里k1.k2是1，2……n的某一排列

       x[n/2]=k[1];

       r=n/2+1;

       l=n/2-1;

       for(i=2,i<=n,i+=2)

       {

              x[r]=k[i];

                     r++;

       }

       for(i=3,i<=n,i+=2)

       {

              x[l]=k[i];

              l--;

       }

}