题解：P9863 [POI 2021/2022 R2] arm

P9863 [POI 2021/2022 R2] arm

题目大意

初始时你有

1

个物品，你需要将物品的数量按若干次以下步骤增加到大于

n

个。

选择 $1$ ：将物品数量存储进数据库中，耗费 $a$ 的时间。
选择 $2$ ：使物品数量增加等同于数据库中的数量，耗费 $b$ 的时间。

初始时数据库为空，问最小操作次数。

观察

操作序列可以划分为多个阶段，每个阶段包含：

一次存储操作（耗时 $a$ ）
若干次增加操作（每次耗时 $b$ ）

假设进行

k

阶段操作，第

i

阶段使用了

1

次存储操作、

Xi

次增加操作，则：

由于第一阶段的操作前有一个物品，因此第一次操作后的物品数量为 $1+X1$ ;
以上一阶段操作后的物品数量为一份，以后的每第 $i （i>1）$ 次操作都会使得物品数量增加 $Xi$ 倍，即乘 $1+Xi$ 。

综上可得，物品增长模式为：

最终数量 $= (1 + x₁) × (1 + x₂) × ... × (1 + xₖ)$

数学优化

因此，对于固定的阶段数

k

，我们不难想到以下条件：

乘积 $≥ n+1$
总时间 $= k×a + (∑xᵢ)×b$ 最小

接下来就很明显了，考虑使用二分的方法完成，具体请见代码。

代码详解

CPP

#include<bits/stdc++.h>
#define imx __int128
using namespace std;
imx n,a,b,ans,l,r,now;
// 安全计算x的k次方，防止溢出
imx spw(imx x,imx k){
    imx p=1;
    for(imx i=1;i<=k;i++){
        if(p>n) return n+2;    // 已超过n，提前返回
        p*=x;
        if(p>n) return n+2;    // 再次检查是否溢出
    }
    return p;
}

// __int128输入输出函数
imx iread(){
    imx x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+(ch-'0');
        ch=getchar();
    }
    return x*f;
}
void iprint(imx x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9) iprint(x/10);
    putchar(x%10+'0');
    return;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    n=iread(),a=iread(),b=iread();
    // 初始答案：单阶段策略（存储1次，增加n次）
    ans=a+n*b;
    // 枚举阶段数k（从2到60）
    // 60是上限因为2^60 ≈ 1.15e18 > 1e18
    for(imx k=2;k<=60;k++){
        // 二分查找：找到最大的base使得base^k ≤ n+1
        l=1,r=n+1,now=1;
        while(l<=r){
            imx mid=(l+r)/2;
            if(spw(mid,k)<=n+1)
                now=mid,l=mid+1;
            else r=mid-1;
        }
        // 尝试不同的因子组合：now和now+1
        for(imx i=0;i<=k;i++){
            imx p1=spw(now,k-i);   // now^(k-i)
            imx p2=spw(now+1,i);   // (now+1)^i
            // 检查乘积是否满足条件
            if(p1>n||p2>n){
                // 单个因子已超过n
                imx t=now*(k-i)+(now+1)*i;  // 因子和
                ans=min(ans,k*a+(t-k)*b);   // 总时间
                break;
            }
            else{
                // 检查乘积是否会溢出或满足条件
                if(p2>0&&p1>(n+1)/p2){
                    imx t=now*(k-i)+(now+1)*i;
                    ans=min(ans,k*a+(t-k)*b);
                    break;
                }
                else if(p1*p2>=n+1){
                    // 乘积满足条件
                    imx t=now*(k-i)+(now+1)*i;
                    ans=min(ans,k*a+(t-k)*b);
                    break;
                }
            }
        }
    }
    iprint(ans);
    return 0;
}

关键

此题必须使用 $__int128$ 类型，部分编译器可能无法编译运行（例如我的Dev-C++ 6.5），不过洛谷的评测机是OK的；
如果要使用 $__int128$ ，必须用快读快写（即函数iread、iprint) !!! (吃掉我好几发CE)；
安全计算 $k$ 的次方，注意溢出。

题解：P9863 [POI 2021/2022 R2] arm

文章操作

P9863 [POI 2021/2022 R2] arm

题目大意

观察

数学优化

代码详解

关键

相关推荐

评论

题解：P9863 [POI 2021/2022 R2] arm