Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-10

WindowWasher

| 14:08

問題文

窓掃除にかかる最短時間を求める。Level-3の問題なのに、あっさり解けてしまった。良い解法がすぐに思いつけば、これぐらいの速度で解けるのか。個人的にはLevel-2の問題の方が難しく感じた。

881.11/1100 - 00:14:58

class WindowWasher {
    public:
        int fastest(int width, int height, vector <int> washTimes) {
            const int numPeople = washTimes.size();
            for (int i = 0; i < numPeople; i++) 
                washTimes[i] *= height;
            vector<int> workTimes(numPeople, 0);
            while (width-- > 0) {
                int minIdx=-1, minTime=INT_MAX;
                for (int i = 0; i < numPeople; i++) {
                    int time = workTimes[i] + washTimes[i];
                    if (time < minTime) {
                        minTime = time;
                        minIdx = i;
                    }
                }
                workTimes[minIdx] += washTimes[minIdx];
            }
            return *max_element(workTimes.begin(), workTimes.end());
        }
};