专栏文章

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

TTFX_Y
P9863题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@min6f6hk
此快照首次捕获于
2025/12/01 21:20
3 个月前
此快照最后确认于
2025/12/01 21:20
3 个月前
查看原文

思路

我们发现，最优策略一定是先进行选择 22，再进行 x1x_1 次选择 11，然后继续进行选择 22，再进行 x2x_2 次选择 1⋯1 \cdots
那么我们设当前物品数量为 nn，则在进行 x1x_1 次选择 11 之后，物品数量就会变为 n×(x1+1)n \times (x_1 + 1)，之后进行选择 22，再进行 x1x_1 次选择 11，物品数量就会变为 n×(x1+1)×(x2+1)⋯n \times (x_1 + 1) \times (x_2 + 1) \cdots
所以最后的结果一定为 1×(x1+1)×(x2+1)×⋯×(xk+1)1 \times (x_1 + 1) \times (x_2 + 1) \times \dots \times (x_k + 1)，而且 kk 一定小于等于 6464。
因此，我们可以枚举 kk（相当于枚举进行了多少次选择 22），对所有答案取最小值。
对于每个 kk，通过贪心我们可以发现当每个 (xi+1)(x_i + 1) 约为 nk\sqrt[k]{n} 时，所消耗的 ∑i=1kxi\sum_{i=1}^{k} x_i 是最小的。
设 m=⌊nk⌋m = \lfloor \sqrt[k]{n} \rfloor，num=1×∏i=1tm×∏i=t+1k(m+1)num = 1 \times \prod_{i=1}^t m \times \prod_{i=t+1}^k (m + 1)。那么，最优解一定为所有 numnum 中大于 nn 的最小的那个数，也就是我们要求最大的那个 tt。而 tt 最大不超过 kk，因此我们直接枚举 tt 即可。
最后的答案即为最小的 a×k+∑i=1kb×(xi−1)a \times k + \sum_{i=1}^{k} b \times (x_i - 1)。
但是，注意到有可能会有浮点误差 pow(n, 1.0 / k) 或溢出问题，因此要加上一句 return LONG_LONG_MAX;。其实本应该写二分的，但是本人不会写，加个特判也能过。

代码

CPP
#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;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...