【Baltic 2011】Meetings / 题解

题目描述

红包举办了一场才艺大赛,有 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);
}
Show Comments