SRM 481 div2 hard: BatchSystem

問題

TopCoder Statistics - Problem Statement

解法

user ごとに, タスクの合計時間が決まります。
合計時間が短いものから順にタスクをこなしていくのが明らかに最適なので, そのように並べましょう。

class BatchSystem {
public:
    vector <int> schedule(vector <int> duration, vector <string> user) {
        map<string, vector<pii> > mp;
        int n = duration.size();
        for (int i = 0; i < n; i++) {
            mp[user[i]].emplace_back(duration[i], i);
        }
        vector<pair<ll, vi> > P;
        for (auto el : mp) {
            ll sum = 0;
            vi v;
            for (pii e : el.second) {
                sum += e.first;
                v.push_back(e.second);
            }
            sort(v.begin(), v.end());
            P.push_back(make_pair(sum, v));
        }
        sort(P.begin(), P.end());
        vi ret;
        for (auto el : P) {
            for (int e : el.second) ret.push_back(e);
        }
        return ret;
    }
};