P9360 [ICPC 2022 Xi'an R] Clone Ranran

解题思路

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

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

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

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

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

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

$$\min_{n=0}^{30}\left(an+b\left\lceil\frac{c}{2^n}\right\rceil\right)$$

参考代码

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