SRM486 Div1 Medium

450

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

view plainprint?

1. map< vector<int>, double > memo;  
2.   
3. class QuickSort {  
4. public:  
5.   double getEval(vector <int> L)  
6.   {  
7.     if (L.size() < 2) return 0;  
8.     if (memo.count(L)) return memo[L];  
9.     double e = 0;  
10.     for (int i = 0; i < L.size(); ++i) {  
11.       int p = L[i];  
12.       vector<int> small;  
13.       vector<int> large;  
14.       for (int j = 0; j < L.size(); ++j) {  
15.         if (L[j] < p) small.push_back(L[j]);  
16.         if (p < L[j]) large.push_back(L[j]);  
17.       }  
18.       int cost = 0;  
19.       for (int j = 0; j < i; ++j) {  
20.         if (p < L[j]) ++cost;  
21.       }  
22.       for (int j = i + 1; j < L.size(); ++j) {  
23.         if (L[j] < p) ++cost;  
24.       }  
25.       e += (double)(getEval(small) + getEval(large) + cost) / L.size();  
26.     }  
27.     return memo[L] = e;  
28.   }  
29. };  

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;
  }
};