SRM481 Div1 Medium

500

ます、同じ人のタスクは連続して処理されるべき。
混ぜると、同じ時間の消費でも互いの終了時刻が後ろにずれてしまう。

どれから最初に処理すべきかというと、時間の総和が小さい順。
逆だと、同じ時間の消費でも終了時刻が後ろにずれてしまう。

同じ時間同士の場合は、1/2して期待値に足す。
どちらが先に行われるかは等確率なので、それより前の場合と後の場合になる。

同じ人のタスクの中での期待値も同様の理由から、1/2にして期待値に足す。

view plainprint?

1. class BatchSystemRoulette {  
2. public:  
3.   vector <double> expectedFinishTimes(vector <int> D, vector <string> U)  
4.   {  
5.     const int N = D.size();  
6.     map<string, lli> sum;  
7.     vector<string> name;  
8.     for (int i = 0; i < N; ++i) {  
9.       name.push_back(U[i]);  
10.       sum[U[i]] += D[i];  
11.     }  
12.     sort(name.begin(), name.end());  
13.     name.erase(unique(name.begin(), name.end()), name.end());  
14.   
15.     vector<double> ret;  
16.     for (int i = 0; i < N; ++i) {  
17.       double prev = 0;  
18.       double same = -sum[U[i]];  
19.       for (int j = 0; j < name.size(); ++j) {  
20.         if (sum[name[j]] <  sum[U[i]]) prev += sum[name[j]];  
21.         if (sum[name[j]] == sum[U[i]]) same += sum[name[j]];  
22.       }  
23.       double e = D[i];  
24.       for (int j = 0; j < N; ++j) {  
25.         if (i != j && U[i] == U[j]) e += 0.5 * D[j];  
26.       }  
27.       ret.push_back(prev + e + same / 2.0);  
28.     }  
29.   
30.     return ret;  
31.   }  
32. };  

class BatchSystemRoulette {
public:
  vector <double> expectedFinishTimes(vector <int> D, vector <string> U)
  {
    const int N = D.size();
    map<string, lli> sum;
    vector<string> name;
    for (int i = 0; i < N; ++i) {
      name.push_back(U[i]);
      sum[U[i]] += D[i];
    }
    sort(name.begin(), name.end());
    name.erase(unique(name.begin(), name.end()), name.end());

    vector<double> ret;
    for (int i = 0; i < N; ++i) {
      double prev = 0;
      double same = -sum[U[i]];
      for (int j = 0; j < name.size(); ++j) {
        if (sum[name[j]] <  sum[U[i]]) prev += sum[name[j]];
        if (sum[name[j]] == sum[U[i]]) same += sum[name[j]];
      }
      double e = D[i];
      for (int j = 0; j < N; ++j) {
        if (i != j && U[i] == U[j]) e += 0.5 * D[j];
      }
      ret.push_back(prev + e + same / 2.0);
    }

    return ret;
  }
};