专栏文章

题解：AT_abc224_g [ABC224G] Roll or Increment

zzxdjmq
AT_abc224_g题解参与者 1已保存评论 1

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@miqimy8b
此快照首次捕获于
2025/12/04 05:25
3 个月前
此快照最后确认于
2025/12/04 05:25
3 个月前
查看原文

ABC224G.Roll or Increment

更好的阅读体验

题意：

有一个 NN 面的骰子，掷出 11 到 NN 的概率相等。初始数字为 SS，目标数字为 TT。有两种操作：
  1. 花费 AA，使当前数字加一；
  2. 花费 BB，重掷。
询问最优策略下到达 TT 的期望花费。
1≤S,T≤N≤109,1≤A,B≤1091 \le S,T \le N \le 10^9,1\le A,B \le 10^9

解法：

由于操作 2 前的操作 1 是无效的，所以最优策略一定分为两部分：
  1. 一直进行操作 2 使当前数字距离 TT 足够近（或在 S≤TS\leq T 且距离足够近时不进行操作 2）；
  2. 一直进行操作 1 使当前数字到达 TT。
足够近的概念比较模糊，所以我们定义足够近为当前数字小于 TT 且二者差小于等于 KK，那么当数字落在区间 [T−K,T][T-K,T] 内时达到足够近条件，于是我们可以得到期望花费为 BNK+1+1K+1×A×∑i=T−KT(T−i)\frac{BN}{K+1}+\frac{1}{K+1}\times A\times \sum\limits_{i=T-K} ^T (T-i)，即 BNK+1+AK2\frac {BN}{K+1}+\frac{AK}{2}。
观察到这个式子里只有 KK 未确定，且形式非常像均值不等式里的 x+1xx+\frac{1}{x}，故考虑使用均值不等式去掉 KK：
BNK+1+AK2=BNK+1+A(K+1)2−A2≥2BNK+1⋅A(K+1)2−A2≥2ABN−A2\begin{aligned} \frac {BN}{K+1}+\frac{AK}{2}&=\frac {BN}{K+1}+\frac{A(K+1)}{2}-\frac{A}{2} \\ &\geq2\sqrt{\frac {BN}{K+1} \cdot \frac{A(K+1)}{2}}-\frac{A}{2}\\&\geq\sqrt{2ABN}-\frac{A}{2}\end{aligned}
当 BNK+1=A(K+1)2\frac {BN}{K+1}=\frac{A(K+1)}{2} 即 K=2BNA−1K=\sqrt{\frac{2BN}{A}}-1 时取等。
但是发现在 N<A2BN < \frac{A}{2B} 或 N>AT22BN>\frac{AT^2}{2B} 时取等条件不能成立，由于 BNK+1+AK2\frac {BN}{K+1}+\frac{AK}{2} 在前两个情况下在区间 [0,T−1][0,T-1] 具有单调性，所以将 K=0K=0 或 T−1T-1 算一下即可。
代码如下：
CPP
#include<bits/stdc++.h>
using namespace std;
#define ld long double
ld n,s,t,a,b,ans;

inline ld cal(int k){
    return 1.0*b*n/(k+1)+1.0*a*k/2.0;
}

int main(){
    cin>>n>>s>>t>>a>>b;
    ans=min(cal(0),cal(t-1));

    if(s<=t)ans=min(ans,a*(t-s));

    int mink=sqrtl(2.0*b*n/a)-1;
    if(mink>=0 && mink<t)ans=min(ans,cal(mink));
    if(mink-1>=0 && mink-1<t)ans=min(ans,cal(mink-1));
    if(mink+1>=0 && mink+1<t)ans=min(ans,cal(mink+1));

    printf("%.16Lf\n",ans);
    return 0;
}

评论

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

正在加载评论...