SRM486 Div1 Medium

450

実際にソートしながら試す。

map< vector<int>, double > memo;

class QuickSort {
public:
  double getEval(vector <int> L)
  {
    if (L.size() < 2) return 0;
    if (memo.count(L)) return memo[L];
    double e = 0;
    for (int i = 0; i < L.size(); ++i) {
      int p = L[i];
      vector<int> small;
      vector<int> large;
      for (int j = 0; j < L.size(); ++j) {
        if (L[j] < p) small.push_back(L[j]);
        if (p < L[j]) large.push_back(L[j]);
      }
      int cost = 0;
      for (int j = 0; j < i; ++j) {
        if (p < L[j]) ++cost;
      }
      for (int j = i + 1; j < L.size(); ++j) {
        if (L[j] < p) ++cost;
      }
      e += (double)(getEval(small) + getEval(large) + cost) / L.size();
    }
    return memo[L] = e;
  }
};