SRM 481 Div2 Hard BatchSystem

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=10808&rd=14234

バッチシステムであるジョブiをこなすのに必要な時間duration[i]とこの仕事をおこなう者の名前user[i]が与えられる。user[i]が与えられた仕事を終えるまでに待たねばならない時間とはバッチシステムが開始してから自身のジョブが終了するまでである。バッチシステムは一度に一つのジョブしか行えない。たとえばjohnが100かかるジョブを、Smithが200かかるジョブをこの順番で処理するときJohnは100、smithは100 + 200 = 300待たねばならない。各人のジョブが終了するまでに各人が待つ平均時間を最小化するようなジョブの順番を返せ。

やりかた

貪欲でいける。
あるユーザのジョブの合計時間が短い順にジョブを処理すればいい。やりかたとしてはある人間が行うジョブ番号（昇順）及びジョブ時間の合計を保持しておく。あとは合計時間でソートして、ジョブ合計時間の最も短いもののジョブ番号から順に列挙していけばいい。

ジョブの合計時間が同じ者が複数人いた場合、STLのsortを使うと不安定ソートなため順番が前後してしまうことがあるのでstable_sortを使用する。

以下ソース。

struct man{
  string name;
  vector<ll> jobID;
  ll sum;
  bool operator<(const man &r)const{
    return sum < r.sum;
  }
};

class BatchSystem {
public:
  vector <int> schedule(vector <int> duration, vector <string> user) {
    int N = duration.size();
    vector <man> work;
    for(int i = 0; i < N; i++){
      int idx = -1;
      for(int j = 0; j < (int)work.size(); j++){
	if(work[j].name == user[i]) idx = j;
      }
      //found
      if(idx >= 0){
	work[idx].jobID.push_back(i);
	work[idx].sum += duration[i];;
      }else{ //not found
	man a;
	a.name = user[i];
	a.jobID.push_back(i);
	a.sum = duration[i];
	work.push_back(a);
      }
    }
    
    stable_sort(ALL(work));

    vector<int> ans;
    for(int i = 0; i < (int)work.size(); i++)
      for(int j = 0; j < (int)work[i].jobID.size(); j++)
	ans.push_back(work[i].jobID[j]);
    return ans;
  }
};

普通のsortで出してWA。stable_sortで出して無事AC。
stable_sortって初めて使ったお（^ω^）

追記
2度めはintオーバーフローをやらかした。うわあ。