自动搬运

查看原文

来自洛谷，原作者为

	TruchyR ¿啥你问了我我问了你啥?

搬运于2025-08-24 22:52:31，当前版本为作者最后更新于2023-12-06 23:23:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Part 1 思路

首先我们转化一下题目：
造一个长度为 $k$ 的数组 $p$ 满足 $\prod_{i=1}^{k} p_i>n$，使得 $ak+b(-k+\sum_{i=1}^{k} p_i)$ 最小。
（每个 $p_i$ 表示做 $1$ 次 $1$ 操作和 $p_i-1$ 次 $2$ 操作，可以把物品翻到原来的 $p_i$ 倍。）
默认下文中的 $p$ 是从小到大排好序的。
给出一个结论：在至少一个最优方案中，$p_k-p_i\leq 1$。
简单说明：确定了 $\sum_{i=1}^{n}p_i$ 的值后，我们一定可以让这些数尽量接近让他们的乘积最大。
容易发现 $k\leq\left \lfloor \log{n} \right \rfloor$，毕竟 $p_i=1$ 是没有任何好处的，
我们可以考虑枚举 $k$：

• 对于枚举的 $k$，我们可以钦定 $p_i=p_k$，这样我们二分一个 $p_k$ 即可。
• 最终答案显然可以不满足 $p_i=p_k$，这时我们一个个尝试将 $p_i\rightarrow p_i-1$，来最小化答案。
• 对于每个 $k$ 可以得到一个方案，把它们取最小值即可。

这道题就这么做完了。

Part 2 代码

注意答案上界，以及 $m=1$ 时二分上界是 $n+1$。

#include<bits/stdc++.h>
#define int __int128
using namespace std;
long long N,A,B;
int n,a,b,ans=1;
int check(int x,int y){
	int z=1;
	while(y){
		if(z*x>n) return 1;
		z*=x;y--;
	}return 0;
}
signed main(){
	cin.tie(0);cout.tie(0);
	cin>>N>>A>>B;n=N;a=A;b=B;//赋初值
	for(int i=1;i<=15;i++) ans*=10;
	for(int i=1;i<=63;i++){
		int l=1,r=n+1,z=1,res=0;
		//找到最小的整数 r 使得 (r**i)>n
		while(l<r){
			int mid=(l+r)>>1;
			if(check(mid,i)) r=mid;
			else l=mid+1;
		}
		//计算 r**i
		for(int j=1;j<=i;j++) z*=r;
		//计算目前的贡献
		res=i*(a+b*(r-1));
		//尽可能多的把 r→(r-1)
		for(int j=1;j<i;j++){
			if(z/r*(r-1)>n){
				z=z/r*(r-1);
				res-=b;
			}else break;
		}
		//更新答案
		ans=min(res,ans);
	}cout<<(long long)ans;
    return 0;
}