题目描述
红包举办了一场才艺大赛，有 n 个人参加。每个人表演需要 p 分钟，最后评审需要 v 分钟才能评选出第一名。
然而这样一共就需要 pn + v 分钟。红包觉得太慢了，于是决定通过分轮加快速度。 每轮把剩下的人分成一些组，然后同时进行比赛，然后留下第一名。 等这一轮的全部比完，就进行下一轮。 直到只剩下一个人为止。
求最少需要多少时间。 可以认为评委个数以及场地数无限。
思路
枚举进行的轮数 $k$。对于每个 $k$，最初一定分成了 $\sqrt[k]{n}$ 组。直接向下取整计算即可， 不足 $n$ 个人就逐个补齐。
代码
#include <bits/stdc++.h>
#define ll long long
ll n,p,v,k,ans=LLONG_MAX;
ll read(){
ll x=0,flag=1;char ch=getchar();
while(!isdigit(ch)&&ch!='-') ch=getchar();
if (ch=='-') flag=-1,ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-'0'),ch=getchar();
return x*flag;
}
void dec(ll &x,ll y){x>y?x=y:0;}
void Check(){
ll x=pow(n,1./k);
ll w=1,c=0;
for (ll i=1;i<=k;++i)
w*=x,c+=x;
while(w<n) w=w/x*(x+1),c++;
dec(ans,c*p+k*v);
}
int main(){
n=read(),p=read(),v=read();
for (k=1;k<log(n)/log(2.0);++k)
Check();
printf("%lld\n",ans);
}