题解：P9360 [ICPC2022 Xi'an R] Clone Ranran

lailai0916 · 2023-05-23 22:21:46 · 题解

解题思路

显然，操作一在操作二之前进行更具性价比。

因此，最合理的策略是优先执行若干次操作一，然后再进行操作二。

可以枚举操作一的执行次数：

• 如果执行 n 次操作一，可以得到 2^n 个人，所需时间为 an。
• 这 2^n 个人出 c 道问题，每道题 b 分钟，所需时间为 b\left\lceil\frac{c}{2^n}\right\rceil。

最多会执行 30 次操作一，因为 2^{30}>10^9 人已经足够多。

通过枚举所有可能的执行次数，计算每种情况下所需的总时间并取最小值，即：

参考代码

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

using ll=long long;
const ll inf=0x3f3f3f3f3f3f3f3f;
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=inf;
        for(int i=0;i<=30;i++)
        {
            ans=min(ans,i*a+(c+(1ll<<i)-1)/(1ll<<i)*b);
        }
        cout<<ans<<'\n';
    }
    return 0;
}