小欧喝水

[题目链接](https://www.nowcoder.com/practice/b5c4d567ca6a450eae7bee2852078b10)

思路

本题是一道概率期望题。 个杯子中 个有水，每轮随机选一个杯子：选到空杯则什么都不做；选到满杯且上一轮喝过水也什么都不做；选到满杯且上一轮没喝水则喝掉。求喝完所有水的期望轮数。

状态定义

设 为还剩 杯水、上轮没喝水时的期望轮数， 为还剩 杯水、上轮喝了水时的期望轮数。

边界：（水已喝完）。

推导

上轮喝了水，这一轮无论选到什么杯子都不会喝：

  • 选到满杯（概率 ）：不能喝，转到
  • 选到空杯（概率 ）：什么都不做，转到

两种情况都转到 ，因此：

$$

推导

上轮没喝水，选到满杯就会喝：

$$

移项解出：

$$

$$

展开递推

将 代入：

$$

$$

逐层展开得到闭式：

$$

其中 是第 个调和数。

样例验证

  • ：
  • ：
  • ：

全部吻合。

复杂度

  • 时间复杂度：，计算调和数求和
  • 空间复杂度：

代码

#include <cstdio>
using namespace std;

int main() {
    long long n, m;
    scanf("%lld%lld", &n, &m);
    double ans = m - 1;
    for (long long k = 1; k <= m; k++) {
        ans += (double)n / k;
    }
    printf("%.9f\n", ans);
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long m = sc.nextLong();
        double ans = m - 1;
        for (long k = 1; k <= m; k++) {
            ans += (double) n / k;
        }
        System.out.printf("%.9f%n", ans);
    }
}

import sys

def main():
    n, m = map(int, sys.stdin.readline().split())
    ans = m - 1.0
    for k in range(1, m + 1):
        ans += n / k
    print(f"{ans:.9f}")

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });

rl.on('line', (line) => {
    const [n, m] = line.trim().split(' ').map(Number);
    let ans = m - 1;
    for (let k = 1; k <= m; k++) {
        ans += n / k;
    }
    console.log(ans.toFixed(9));
    rl.close();
});