题解归档 - cf104077C

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf104077C
• 本地来源：problems/cf104077C/idea.md
• 题目链接：https://codeforces.com/gym/104077/problem/C
• 原始标题：C - Clone Ranran

思路

C - Clone Ranran

If we decide to have at least w Ranrans before producing problems, the fastest way is to clone
in parallel for ceil(log2 w) rounds. Then the w workers can produce ceil(c/w) batches of
problems, each batch taking b minutes.

So the answer is

min_k k*a + ceil(c / 2^k)*b

over clone rounds k. It is enough to try k <= 62, and we stop once 2^k >= c.

Checked against a small BFS/DP oracle for small values.

代码

来源：problems/cf104077C/solution.cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        ll a, b, c;
        cin >> a >> b >> c;
        ll ans = c * b;
        for (int k = 0; k <= 62; k++) {
            ll workers;
            if (k >= 61) workers = (ll)4e18;
            else workers = 1LL << k;
            ll batches = (c + workers - 1) / workers;
            ans = min(ans, a * k + b * batches);
            if (workers >= c) break;
        }
        cout << ans << '\n';
    }
    return 0;
}