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

· · 题解

思路

我们发现，最优策略一定是先进行选择 2，再进行 x_1 次选择 1，然后继续进行选择 2，再进行 x_2 次选择 1 \cdots

那么我们设当前物品数量为 n，则在进行 x_1 次选择 1 之后，物品数量就会变为 n \times (x_1 + 1)，之后进行选择 2，再进行 x_1 次选择 1，物品数量就会变为 n \times (x_1 + 1) \times (x_2 + 1) \cdots

所以最后的结果一定为 1 \times (x_1 + 1) \times (x_2 + 1) \times \dots \times (x_k + 1)，而且 k 一定小于等于 64。

因此，我们可以枚举 k（相当于枚举进行了多少次选择 2），对所有答案取最小值。

对于每个 k，通过贪心我们可以发现当每个 (x_i + 1) 约为 \sqrt[k]{n} 时，所消耗的 \sum_{i=1}^{k} x_i 是最小的。

设 m = \lfloor \sqrt[k]{n} \rfloor，num = 1 \times \prod_{i=1}^t m \times \prod_{i=t+1}^k (m + 1)。那么，最优解一定为所有 num 中大于 n 的最小的那个数，也就是我们要求最大的那个 t。而 t 最大不超过 k，因此我们直接枚举 t 即可。

最后的答案即为最小的 a \times k + \sum_{i=1}^{k} b \times (x_i - 1)。

但是，注意到有可能会有浮点误差 pow(n, 1.0 / k) 或溢出问题，因此要加上一句 return LONG_LONG_MAX;。其实本应该写二分的，但是本人不会写，加个特判也能过。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,a,b,ans=LONG_LONG_MAX;

int solve(){
    int num=pow(n,1.0/k);
    for(int i=k;i>=0;i--){
        int sum=1,cst=0;
        for(int j=1;j<=i;j++){
            sum*=num;
            cst+=(num-1);
        }
        for(int j=i+1;j<=k;j++){
            sum*=(num+1);
            cst+=num;
        }
        if(sum>=n||sum<0) return b*cst+a*k;
    }
    return LONG_LONG_MAX;
}

signed main(){
    cin>>n>>a>>b;
    n++;
    for(int i=1;i<=64;i++){
        k=i;
        int t=solve();
        if(t>=0) ans=min(ans,t);
    }
    cout<<ans;
    return 0;
}