P9863 题解

TruchyR · 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;
}