问题描述:

这道题目贪心的思想就在于将使用频率最高的尽可能放在一起。换句话说,使得存储最优的情况,就是期望距离最小的情况是在两两概率最大时候,两两之间的距离最小。要达到这种情况,只有当中间的是最大的文件,从中间到两边文件依次减小,就可以实现了。思路有了算法其实很简单:

#include<fstream>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
bool comp(const double a,const double b)
{
  return a>b;
}
int abs(int a)
{
  if(a>0)
  {
    return a;
  }else
  {
    return -a;
  }
}
int main()
{
  const int MAXN=20000;
  ifstream fin("input.txt");
  ofstream fo("output.txt");
  int n;
  vector<int>num;
  vector<double>prob;
  vector<double>stoed;
  double sum=0.0;
  fin>>n;
  for(int i=0;i<n;i++)
  {
    int numCur;
    fin>>numCur;
    num.push_back(numCur);
    sum+=numCur;
    stoed.push_back(0);
  }
  for(int i=0;i<n;i++)
  {
    prob.push_back(num[i]/sum);
  }
  sort(prob.begin(),prob.end(),comp);
  int cnt=0;
  for(int i=0;i<n/2;i++)
  {
    stoed[n/2+i]=prob[cnt];cnt++;
    stoed[n/2-i-1]=prob[cnt];cnt++;  
  }
  if(cnt<n)
  {
    stoed[cnt]=prob[cnt];
  }
  double res=0;
  for(int i=0;i<n;i++)
  {
    for(int j=0;j<n;j++)
    {
      if(i<j)
      {
        res+=stoed[i]*stoed[j]*abs(i-j);
      }
    }
  }
  fo<<res<<endl;
  return 0;
}

整个算法时间复杂度最大的地方在求和处,是O(n^2),排序复杂度是O(nlogn),其他复杂度最多也就O(n)了。所以总时间复杂度为O(n^2)