SRM481 Div1 Medium

500

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

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

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

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

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