Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-11

FairWorkload

| 13:17

問題文

仕事をなるべく均等になるように割り振る。良問。Level-2の問題より解きやすかった。

532.87/1000 - 00:32:37

class FairWorkload {
    public:
        int getMostWork(vector <int> folders, int workers) {
            amounts = vector<int>(workers, 0);
            maxOptimalAmount = INT_MAX;
            go(folders, 0, workers, 0);
            return maxOptimalAmount;
        }
    private:
        int maxOptimalAmount;
        vector<int> amounts;
        void go(const vector<int>& folders, const int f_id, 
                const int workers, const int w_id) {
            if (f_id == folders.size()) {
                for (int i = 0; i < workers; i++)
                    if (amounts[i] == 0)
                        return;
                maxOptimalAmount = min(maxOptimalAmount, 
                        *max_element(amounts.begin(),amounts.end()));
                return;
            }
            if (maxOptimalAmount <= amounts[w_id]) return;
            if (w_id == workers) return;
            amounts[w_id] += folders[f_id];
            go(folders, f_id+1, workers, w_id);
            amounts[w_id] -= folders[f_id];
            if (w_id+1 == workers) return;
            amounts[w_id+1] += folders[f_id];
            go(folders, f_id+1, workers, w_id+1);
            amounts[w_id+1] -= folders[f_id];
        }
};

OliviaOlivia2011/07/09 22:49Ppl like you get all the birans. I just get to say thanks for he answer.

cganpmvkaacganpmvkaa2011/07/10 00:21ozUmeq <a href="http://pjfcqeeeqmnr.com/">pjfcqeeeqmnr</a>

gkbfwfvcbgkbfwfvcb2011/07/10 21:09Bo1aDa , [url=http://xrkdnugczyzj.com/]xrkdnugczyzj[/url], [link=http://sbngsfqxhlpy.com/]sbngsfqxhlpy[/link], http://safjlfwoassi.com/

uxpnpunauxpnpuna2011/07/11 20:32crHIwv <a href="http://fodsgqzsvyim.com/">fodsgqzsvyim</a>

mhhaaumhhaau2011/07/12 21:58da56vU , [url=http://tqvvgrxdnlwt.com/]tqvvgrxdnlwt[/url], [link=http://ofcuaexemicz.com/]ofcuaexemicz[/link], http://shzifphpejdh.com/