BatchSystem srm 481 div2 hard

• 基本的には、全ジョブの所要時間合計が少ないユーザのジョブから実行すれば良い。
• 但し、辞書式順で最小のものを返すために、次のようなソート処理を行った。
  • 各ジョブ番号iに対して [user[i]の全ジョブの所要時間合計, user[i]が最初に出てくるジョブ番号, i(ジョブ番号自身)]という三つ組を作り、これらを左側の要素優先でソート。

#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>
#include <stdexcept>


using namespace std;


class BatchSystem{
  class MyComp{
  public:
    bool operator()(vector<long long> r, vector<long long> l){
      int i;
      for(i = 0; i < 3; i++){
	if(r[i] != l[i]) break;
      }
      if(i == 3) return false;
      return r[i] < l[i];
    }
  };


public:

  vector <int> schedule(vector <int> duration, vector <string> user){
    map<string, long long> jobTime;
    map<string, int> firstPos;
    int n = duration.size();

    for(int i = 0; i < n; i++){
      if(jobTime.find(user[i]) == jobTime.end()){
	jobTime[user[i]] = 0;
	firstPos[user[i]] = i;
      }
      jobTime[user[i]] += duration[i];
    }

    vector<vector<long long> > p(n, vector<long long>(3));
    for(int i = 0; i < n; i++){
      p[i][0] = jobTime[user[i]];
      p[i][1] = firstPos[user[i]];
      p[i][2] = i;
    }
    sort(p.begin(), p.end(), MyComp());

    vector<int> ret;
    for(int i = 0; i < n; i++){
      ret.push_back(p[i][2]);
    }
    return ret;
  }



};