Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-07

ParallelSpeedup

| 19:21

問題文

何基のコンピュータを使って、並列処理させた場合が一番速いのかを求める。

388.73/500 - 00:16:33

class ParallelSpeedup {
    public:
        int numProcessors(int k, int overhead) {
            long long minTime = k;
            for (int p = 2; p <= k; p++) {
                const long long time = overhead*calcCommCount(p) 
                    + static_cast<long long>(ceil(static_cast<double>(k)/p));
                if (time >= minTime) 
                    return p-1;
                minTime = time;
            }
            return k;
        }
    private:
        long long calcCommCount(const int p) {
            return static_cast<long long>(p) * (p-1) / 2;
        }
};