题解：AT_abc224_g [ABC224G] Roll or Increment

zxdjmq · 2025-01-14 16:01:22 · 题解

ABC224G.Roll or Increment

更好的阅读体验

题意：

有一个 N 面的骰子，掷出 1 到 N 的概率相等。初始数字为 S，目标数字为 T。有两种操作：

1. 花费 A，使当前数字加一；

2. 花费 B，重掷。

询问最优策略下到达 T 的期望花费。

解法：

由于操作 2 前的操作 1 是无效的，所以最优策略一定分为两部分：

1. 一直进行操作 2 使当前数字距离 T 足够近（或在 S\leq T 且距离足够近时不进行操作 2）；
2. 一直进行操作 1 使当前数字到达 T。

足够近的概念比较模糊，所以我们定义足够近为当前数字小于 T 且二者差小于等于 K，那么当数字落在区间 [T-K,T] 内时达到足够近条件，于是我们可以得到期望花费为 \frac{BN}{K+1}+\frac{1}{K+1}\times A\times \sum\limits_{i=T-K} ^T (T-i)，即 \frac {BN}{K+1}+\frac{AK}{2}。

观察到这个式子里只有 K 未确定，且形式非常像均值不等式里的 x+\frac{1}{x}，故考虑使用均值不等式去掉 K：

当 \frac {BN}{K+1}=\frac{A(K+1)}{2} 即 K=\sqrt{\frac{2BN}{A}}-1 时取等。

但是发现在 N < \frac{A}{2B} 或 N>\frac{AT^2}{2B} 时取等条件不能成立，由于 \frac {BN}{K+1}+\frac{AK}{2} 在前两个情况下在区间 [0,T-1] 具有单调性，所以将 K=0 或 T-1 算一下即可。

代码如下：

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