TopCoder SRM 722 Div2 Hard: MulticoreProcessingEasy

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

CPU が 個あり、 番目の CPU は ミリ秒につき仕事量 を消化でき、コア数は である。

いま、仕事量 のタスクがある。 個ある CPU のうちどれか つだけ選び、このタスクを消費したい。

使うコア数は選ぶことができ、 コア使用する場合は コアあたり の仕事量を割り当て、それを同時に処理することができるが、タスクを処理する時間とは別に、追加で ミリ秒もかかる。

このタスクを終わらせるために必要な秒数の最小値を出力せよ。

解説

原文を見たらわかるのですが問題文がわかりにくく、読解ゲーです。 (誤読で 1 回落としてしまった・・・)

最小化なので二分探索をすればよいです。

使用できる CPU はどれか つなので、まずどれを選ぶかを決め、コアをいくつ使うかを全て試せばよいです。決められた閾値の中で達成できる場合がひとつでもあれば上限を小さく、そうでなければ下限を大きくすればよいです。

切り上げなどの計算に気をつけましょう。

ソースコード

class MulticoreProcessingEasy {
    public:
    int fastestTime(int jobLength, int corePenalty, vector<int> speed, vector<int> cores) {
        vector<pii> cpus;
        int N = speed.size();

        long long int ub = INF, lb = 0;
        while(ub - lb > 1) {
            long long int mid = (ub + lb) / 2;
            bool ok = false;
            for(int i=0; i<N; i++) {
                for(int k=1; k<=cores[i]; k++) {
                    int work_per_core = (jobLength + k - 1) / k;
                    int work_sec = (work_per_core + speed[i] - 1) / speed[i];
                    long long int penalty = work_sec + (k - 1) * corePenalty;
                    if(penalty <= mid) ok = true;
                }
                
            }
            (ok ? ub : lb) = mid;
        }
        return ub;
    }
};