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

原题链接

• 洛谷 P9360 [ICPC2022 Xi'an R] Clone Ranran

解题思路

1. 显然，操作一在操作二之前进行更具性价比。因此，最合理的策略是优先执行若干次操作一，然后再进行操作二。

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

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

3. 最多只会进行 $30$ 次操作一，因为 $2^{30}>10^9$ 人已经足够多。通过枚举所有可能的执行次数，计算每种情况下所需的总时间，并取最小值，即 $\min_{n=0}^{30} (n\cdot a+\left\lceil\frac{c}{2^n}\right\rceil\cdot b)$。

参考代码

#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;
}