SRM481 Div1 Medium(500) BatchSystemRoulette
待ち時間の平均を最小化とあるけどユーザー数は固定なので待ち時間の合計の最小化と同じ。あるユーザーの最後のジョブが終わる時刻がユーザーの待ち時間なので、同じユーザーのジョブはまとめて実行する。また、合計時間が短いユーザーからジョブを実行する。待ち時間を最小化したときに選べるのは、ジョブの合計時間が同じユーザーの実行順序と、同じユーザーのジョブの実行順序。
#include <string> #include <vector> #include <algorithm> #include <utility> using namespace std; class BatchSystemRoulette{public: vector <double> expectedFinishTimes( vector <int> duration, vector <string> user ) { int n = (int)duration.size(); // ユーザー名とそのユーザーのジョブの合計時間 vector<string> name; vector<long long> sum; for ( int i=0; i<n; i++ ) { int p = find( name.begin(), name.end(), user[i] ) - name.begin(); if ( p >= (int)name.size() ) name.push_back( user[i] ), sum.push_back( 0 ); sum[p] += duration[i]; } vector<double> answer( n ); int m = (int)name.size(); for ( int i=0; i<m; i++ ) { double ut = 0; // このユーザーのジョブの開始時刻の期待値 for ( int j=0; j<m; j++ ) if ( j != i ) { if ( sum[j] < sum[i] ) ut += sum[j]; if ( sum[j] == sum[i] ) ut += sum[j] / 2.; } for ( int j=0; j<n; j++ ) if ( user[j] == name[i] ) { double jt = ut; // このジョブの開始時刻の期待値 for ( int k=0; k<n; k++ ) if ( k != j && user[k] == name[i] ) jt += duration[k] / 2.; answer[j] = jt + duration[j]; } } return answer; }};