SRM481 Div2 Hard(900) 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; }};