SRM481 Div2 Hard(900) BatchSystem

BatchSystem

待ち時間の平均を最小化とあるけどユーザー数は固定なので待ち時間の合計の最小化と同じ。あるユーザーの最後のジョブが終わる時刻がユーザーの待ち時間なので、同じユーザーのジョブはまとめて実行する。また、合計時間が短いユーザーからジョブを実行する。合計時間が同じユーザーはより小さいインデックスのジョブを持つユーザーから実行。

#include <string>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

struct USER
{
    string name;
    long long sum;
    int min;
    USER(string n):name(n),sum(0),min(999){}
    bool operator<(const USER &u)const{return sum<u.sum||sum==u.sum&&min<u.min;}
};

class BatchSystem{public:
vector <int> schedule( vector <int> duration, vector <string> user )
{
    int n = (int)user.size();

    //  各ユーザーの合計ジョブ時間と最小インデックスのジョブを求める
    vector<USER> u;
    for ( int i=0; i<n; i++ )
    {
        int j;
        for ( j=0; j<(int)u.size(); j++ )
            if ( u[j].name == user[i] )
                break;
        if ( j >= (int)u.size() )
            u.push_back( USER(user[i]) );
        u[j].sum += duration[i];
        u[j].min = min( u[j].min, i );
    }

    sort( u.begin(), u.end() );

    vector<int> answer;
    for ( int i=0; i<(int)u.size(); i++ )
    {
        for ( int j=0; j<n; j++ )
            if ( user[j] == u[i].name )
                answer.push_back( j );
    }
        
    return answer;
}};