SRM481 Div1 Medium(500) BatchSystemRoulette

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