TopCoderの問題を解く

FairWorkload

SRM 169, Div2, Div2 Level-3, Div1, Div1 Level-2, Brute Force, 55% | 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];
        }
};