数学期望

CF908D

每次以 $P$ 的概率生成字符 0，以 $1-P$ 的概率生成字符 1，并追加到初始为空的字符串末尾。当字符串中子序列 01 的出现次数 $\ge K$ 时停止生成。求最终字符串中 01 子序列出现次数的数学期望。$K \leqslant 1000$

• $f(c, s)$：当前字符串中已经有 $c$ 个字符 0，并且已经构成了 $s$ 个 01 子序列时的答案。
• $f(c, s) = P f(c+1, s) + (1-P) f(c, s+c)$
• $f(c, s) = s \quad (s \ge K)$
• $f(c, s) = s + c + \dfrac{P}{1-P} \quad (c \ge K, s < K)$

CF235B

给定一个长度为 $N$ 的二元序列，第 $i$ 个元素为 $1$ 的概率为 $P_i$，为 $0$ 的概率为 $1 - P_i$。求该序列所有极大连续 $1$ 区间的长度平方之和的数学期望。

• $E_i = E_{i-1} + P_i(2L_{i-1} + 1)$
• $L_i = P_i(L_{i-1} + 1)$

CF2081A

给定 $x$。当 $x > 1$ 时，每次操作等概随机选择 $x \leftarrow \left\lfloor \frac{x}{2} \right\rfloor$ 或 $x \leftarrow \left\lceil \frac{x}{2} \right\rceil$，求使 $x$ 变为 1 的期望操作次数。

设 $f(i, j)$ 表示处理到第 $i$ 位时的期望操作次数，$j \in \{0, 1\}$ 表示当前数值是否有额外的进位加一。

std::array<Z, 2> f {};
f[0] = 0;
f[1] = 1;
for (int i = 1; i < N; i++) {
    std::array<Z, 2> nf {};
    if (S[i] == '0') {
        nf[1] = (f[0] + f[1]) / 2 + 1;
        nf[0] = f[0] + 1;
    } else {
        nf[0] = (f[0] + f[1]) / 2 + 1;
        nf[1] = f[1] + 1;
    }
    f = nf;
}
std::cout << f[0] << "\n";

已知初始状态为 $0$。当处于状态 $i$ 时，进行一步操作：

• 以 $P_i$ 的概率转移到状态 $i+1$。
• 以 $1 - P_i$ 的概率转移回初始状态 $1$。

求从状态 $0$ 首次到达状态 $N$ 的步数的期望。

• $f(n)=\dfrac{1}{P_{n}}[f(n-1) + 1]$
• 答案前缀和 $S(n) = S(n-1) + \dfrac{1}{P_{n}}+\bigg(\dfrac{1}{P_{n}}-1\bigg) f(n-1)$

已知初始状态为 $0$。给定集合 $S$，初始时 $S = \{1\}$ 且 $1$ 始终属于 $S$。当处于状态 $i$ 时，进行一步操作：

• 以 $P_i$ 的概率转移到状态 $i+1$。
• 以 $1 - P_i$ 的概率转移回状态 $g(i) = \max\{x \in S \mid x \le i\}$。

共有 $Q$ 次修改，每次给定 $U$：若 $U \in S$ 则将 $U$ 从 $S$ 中移除，否则将 $U$ 加入 $S$。
求每次修改后，求从状态 $0$ 首次到达状态 $N$ 的步数的期望。

• 若 $i+1 \notin S$，$f(n)=\dfrac{1}{P_{n}}[f(n-1) + 1]$
• 若 $i+1 \in S$，$f(n) = 0$
• 答案前缀和 $S(n) = S(n-1) +\dfrac{1}{P_{n}}+\bigg(\dfrac{1}{P_{n}}-1\bigg) f(n-1)$

构造一个 $1 \times 3$ 的状态行向量 $T(n) = \begin{bmatrix} S(n) & f(n) & 1 \end{bmatrix}$，做矩阵乘法。

CF2040E

$N$ 点有根树。对所有 $v, w$ 求答案 $f(v, w)$：

初始位于节点 $v \ne 0$，拥有数值 $w$。第 $i$ 步：

• 若 $i$ 为奇数，移动到当前节点的父节点。
• 若 $i$ 为偶数，选择以下两种操作之一：
  1. 若 $w > 0$，令 $w \leftarrow w-1$，移动到父节点。
  2. 等概率随机移动到一个相邻节点。

到达节点 0 时停止。

把第 $2k$ 次操作与第 $2k-1$ 次操作看做一次操作。

$$f(v, w) = \min\lbrace f(p_{p_{v}}, w-1)+2, \ f(p_{p_{v}}, w)+2\operatorname{deg}(p_{v}) \rbrace$$

CF2089C

给定 $L$ 把不同的锁和 $L$ 把不同的钥匙，它们之间存在未知的唯一的一一对应关系。初始时，所有合法的一一映射排列概率均等。

有 $N$ 个人按固定顺序周而复始地轮流尝试开锁，直到所有 $L$ 把锁均被打开：

1. 尝试： 每次轮到的玩家选择一把钥匙和一把锁进行测试。
2. 策略： 玩家根据所有已知的历史测试结果，选择当前匹配成功概率最大的（钥匙，锁）组合。若有多个组合概率同为最大，则在其中等概率随机盲选一对。
3. 结果更新： 测试结果全员可见。若成功，该锁与钥匙配对完成，不再参与后续尝试；若失败，排除该组合，概率重新分布。

求：这 $N$ 个人中，每个人成功打开锁次数的期望值。$N \leqslant 100,L \leqslant 5000$。

最优方法是对每个锁孔，拿所有钥匙挨个试一遍。

先设 $N\to \infty$。

设 $f(\ell, k)$：当面对 $l$ 把锁和 $l$ 把钥匙的局面时，在整条时间线的第 $k$ 次尝试这一特定的时刻，有人成功开锁的期望。

考虑递推，已经算出 $\ell-1$ 把锁时的答案 $f(\ell-1,*)$。如果增加一把锁，不妨设第一个人先尝试这把锁。

我们设打开第一把锁之前，失败了 $i$ 次。

如果 $i=k$ 表示

$$f(l, k) = \frac{1}{l} \sum_{i=0}^{l-1} \Big([k=i] + f(l-1, k - i - 1) \Big)$$

不难写出这样的代码：

std::vector<Z> f(L * L);
for (int l = 1; l <= L; l++) {
    Z inv = Z(l).inv();
    std::vector<Z> nf(L * L);
    for (int i = 0; i < l; i++) {
        nf[i] += 1;
        for (int j = 0; j + i + 1 < L * L; j++) {
            nf[j + i + 1] += f[j];
        }
    }
    for (int i = 0; i < L * L; i++) {
        nf[i] *= inv;
    }
    f = nf;
}
std::vector<Z> ans(N);
for (int i = 0; i < L * L; i++) {
    ans[i % N] += f[i];
}

复杂度为 $\operatorname{O}(\ell^{3})$，需要优化。

所需答案的下标是模 $n$ 的，因此上述所有下标均可以在模 $n$ 下运算：

std::vector<Z> f(N);
for (int l = 1; l <= L; l++) {
    Z inv = Z(l).inv();
    std::vector<Z> nf(N);
    for (int i = 0; i < l; i++) {
        nf[i % N] += 1;
        for (int j = 0; j < N; j++) {
            nf[(j + i + 1) % N] += f[j % N];
        }
    }
    for (int i = 0; i < N; i++) {
        nf[i] *= inv;
    }
    f = nf;
}
auto ans = f;

复杂度为 $\operatorname{O}(n^{}\ell^{2})$，仍需要优化。

发现第二层循环的 $x$，有大部分的内层循环完全相同，把这层循环也在模 $n$ 下运算：

std::vector<Z> f(N);
for (int l = 1; l <= L; l++) {
    Z inv = Z(l).inv();
    std::vector<Z> nf(N);
    for (int i = 0; i < N; i++) {
        nf[i] += l / N + (i < l % N);
    }
    for (int j = 0; j < N; j++) {
        for (int i = 0; i < N; i++) {
            nf[(j + i + 1) % N] += (l / N + (i < l % N)) * f[j];
        }
    }
    for (int i = 0; i < N; i++) {
        nf[i] *= inv;
    }
    f = nf;
}

最终复杂度 $\operatorname{O}(n^{2}\ell)$。

期望的線性性質

CF280C. Game on Tree

给定一棵包含 $N$ 个节点的有根树。每次操作会在当前树中，等概率随机选择一个子树删除。求将整棵树删空的期望次数。

即求每个节点被直接选中并删除的概率之和，答案为 $E = \sum \dfrac{1}{d_i+1}$，这里设根节点的深度 $d_1 = 0$。

CCCPC1E

给定一棵树，执行 $M$ 次，随机选择一个节点，长出一个新叶子。求操作后 $\dfrac{1}{N} \sum d_{i}$ 的期望。

2024 杭电多校 1012 - 并

$N$ 个矩形。求随机选取 $K$ 个不同的矩形，其并集的面积的期望。

转化为此区域至少被某个矩形覆盖一次的概率。记 $S_{n}$ 表示有 $n$ 个矩形覆盖的面积和，答案为

$$E = \sum_{n=1}^{N} \left(1 - \dfrac{\binom{N-n}{K}}{\binom{N}{K}} \right) S_{n}$$

2025 ICPC 沈阳 G

给定凸多边形 $P$ 和 $Q$，随机平移 $Q$，在 $P,Q$ 有交的前提下，求 $P,Q$ 交的面积的期望。

设 $v\in \mathbb{R}^2$ 为均匀分布的随机平移向量，$\chi_A(x)$ 为集合 $A$ 的指示函数（若 $x \in A$ 取 1，否则取 0）。

$$\begin{aligned} M &= \{v \in \mathbb{R}^2 \mid P \cap (Q + v) \neq \varnothing\} \\ &= \{v \in \mathbb{R}^2 \mid \exists x \in \mathbb{R}^2, x \in P \land x - v \in Q\} \\ &= \{x - q \mid x \in P, q \in Q\} \\ &= P \oplus (-Q) \end{aligned}$$

$$\begin{aligned} \mathbb{E}[\text{Area}(P \cap (Q + v))] &= \frac{1}{\text{Area}(M)} \iint_{M} \text{Area}(P \cap (Q + v)) \,dv \\ &= \frac{1}{\text{Area}(M)} \iint_{\mathbb{R}^2} \left(\iint_{\mathbb{R}^2} \chi_P(x) \chi_{(Q + v)}(x) \,dx \right) \,dv \\ &= \frac{1}{\text{Area}(M)} \iint_{\mathbb{R}^2} \iint_{\mathbb{R}^2} \chi_P(x) \chi_Q(x - v) \,dx \,dv \\ &= \frac{1}{\text{Area}(M)} \iint_{\mathbb{R}^2} \chi_P(x) \left(\iint_{\mathbb{R}^2} \chi_Q(x - v) \,dv \right) \,dx \\ &= \frac{1}{\text{Area}(M)} \iint_{\mathbb{R}^2} \chi_P(x) \left(\iint_{\mathbb{R}^2} \chi_Q(u) \,du \right) \,dx \\ &= \frac{1}{\text{Area}(M)} \iint_{\mathbb{R}^2} \chi_P(x) \cdot \text{Area}(Q) \,dx \\ &= \frac{\text{Area}(P) \cdot \text{Area}(Q)}{\text{Area}(M)} \end{aligned}$$

复杂度 $\mathcal{O}(M N \log M N)$，也可以用双指针求 Minkowski Sum 做到 $\mathcal{O}(M+N)$。

几何分布

2024 杭电多校 5013 - 飞行棋

格子编号 $0$ 到 $N$。
重复操作直至恰好到达 $N$：
- 等概率随机 $x \in [1, N]$，向 $N$ 走 $x$ 步。
- 如果 $x=N$ 且未恰好抵达 $N$ 则再次随机 $y \in [1, N - 1]$，向 $N$ 走 $y$ 步。
- 若达到 $N$ 还有剩余步数则反向行走。
求恰好抵达 $N$ 的操作次数期望。

在 $0$ 号格时有 $\dfrac{1}{N}$ 直接进入终点。

对另外 $\dfrac{N-1}{N}$ 情况，进入 $1\sim N-1$ 号格。此时，花费 $1$ 的代价恰好抵达 $N$ 的概率是 $\dfrac{1}{N}$，否则继续停留在 $1\sim N-1$ 号格内。因此离开 $1\sim N-1$ 的期望次数是 $N$。

故答案 $1+\dfrac{N-1}{N} N=N-1+\dfrac{1}{N}$。

雜題

2025 春 杭电多校 10 1004 小塔的随机数

初始一个长度为 $N$ 的序列 $p_{i}=i$。
$M$ 次操作：指定子区间 $[L, R]$ 随机打乱。
求操作后逆序对数量的期望。
$N, M \leqslant 500$。

设 $f(i,j)$ 表示位置 $i,j$ 是逆序对的概率。

vector p(n, vector<Z>(n));
while (m--) {
    int l, r;
    cin >> l >> r;
    l--;
    r--;
    for (int i = l; i <= r; i++) {
        for (int j = i + 1; j <= r; j++) {
            p[i][j] = inv2;
        }
    }
    for (int i = 0; i <= l - 1; i++) {
        Z x = 0;
        for (int j = l; j <= r; j++) {
            x += p[i][j];
        }
        x /= (r - l + 1);
        for (int j = l; j <= r; j++) {
            p[i][j] = x;
        }
    }
    for (int i = r + 1; i < n; i++) {
        Z x = 0;
        for (int j = l; j <= r; j++) {
            x += p[j][i];
        }
        x /= (r - l + 1);
        for (int j = l; j <= r; j++) {
            p[j][i] = x;
        }
    }
}
Z ans = 0;
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        ans += p[i][j];
    }
}
cout << ans << endl;

期望 DP

2024 ICPC Online I E. Random Dungeon（期望 DP，贪心优化）

This problem is prepared by jiangly.

Description

给定 $N,C$ 和长度为 $N$ 的数组 $A$。牌堆里 $N$ 张牌，第 $i\ (1 \leqslant i \leqslant N)$ 张牌的分数是 $A_{i}$。玩家随机等概抽取这些牌，每次抽取成本为 $C$，抽取后不放回。每次抽取后可以选择终止游戏并获得这张卡牌的分数，也可以选择继续抽取。求在最佳策略下的期望最终收益（最终分数减去 $C$ 倍抽取次数）。$1 \leqslant N \leqslant 2\times 10^{5}$，$1 \leqslant C,A_{i} \leqslant 10^{9}$。

Node 1

这是一个典型的最优停时期望 DP，倒序考虑。

令 $f(k, S)$ 表示当牌堆中还剩下 $k$ 张牌，且这 $k$ 张牌为集合 $S$ 时，从此刻开始直到游戏结束，最佳策略下的期望最终收益。有转移

$$f(k, S) = - C + \frac{1}{k} \sum_{i \in S} \max \big\lbrace A_i, \ f(k-1, S \setminus \lbrace A_i \rbrace) \big\rbrace$$

边界条件 $f(0, \varnothing) = 0$，答案是 $f(0, U)$。

复杂度 $\mathcal{O}(N \cdot 2^{N})$，期望通过 12 tests。

#include <bits/stdc++.h>
using namespace std;

int main() {
    cout << fixed << setprecision(10);

    int N, C;
    cin >> N >> C;

    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    vector<double> f(1 << N);
    f[0] = 0;
    for (unsigned k = 1; k <= N; k++) {
        for (unsigned s = 0; s < 1 << N; s++) {
            if (popcount(s) != k) continue;
            for (unsigned bit = 0; bit < N; bit++) {
                if (s >> bit & 1) {
                    f[s] += max<double>(A[bit], f[s ^ (1 << bit)]) / k;
                }
            }
            f[s] -= C;
        }
    }
    cout << f.back() << endl;
 
    return 0;
}

Node 2

DP 是暴力，状压 DP 是暴力中的暴力。既然完备模型不可行，就必须寻找简化的方法。

有一个显然的贪心：如果已经扔掉了某张牌，之后如果抽到比这张牌还垃圾的牌，就一定直接扔掉继续游戏，最终结束游戏时手上的牌的分数一定不会比扔掉的低。

这样得到一个 $\mathcal{O}(N^2)$ 的 DP，令 $f(k, j)$ 表示还剩 $k$ 张牌，牌堆里包含最大的 $j$ 张牌但不包含第 $j+1$ 大时，从此刻开始直到游戏结束，最佳策略下的期望最终收益。

不妨先对 $A$ 降序排序，那么有转移

$$f(k, j) = - C + \frac{k-j}{k} \times f(k-1, j) + \frac{1}{k} \sum_{i=1}^j \max \big\lbrace A_{i}, \ f(k-1, i-1)) \big\rbrace$$

之前的转移是

$$f(k, S) = - C + \frac{1}{k} \sum_{i \in S} \max \big\lbrace A_i, \ f(k-1, S \setminus \lbrace A_i \rbrace) \big\rbrace$$

对比一下能看出，唯一的区别是如果抽到比第 $j+1$ 大还小的牌，就直接继续游戏，不再做决策。

复杂度 $\mathcal{O}(N^{2})$。

#include <bits/stdc++.h>
using namespace std;

int main() {
    cout << fixed << setprecision(10);

    int N, C;
    cin >> N >> C;

    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    sort(A.begin(), A.end(), greater());

    vector f(N + 1, vector<double>(N + 1));
    for (int k = 1; k <= N; k++) {
        double sum = 0;
        for (int j = 1; j <= k; j++) {
            sum += max<double>(A[j - 1], f[k - 1][j - 1]);
            f[k][j] = -C + 1.0 * (k - j) / k * f[k - 1][j] + sum / k;
        }
    }
    cout << f[N][N] << endl;    
 
    return 0;
}

值得注意的是，这两个 DP 的中间计算结果完全不同，

$$f(k, j) \neq \max\limits_{\substack{ \lbrace 1,2,\dots j \rbrace \subset S \\ j+1 \notin S \\ |S| = k}} f(k, S)$$

也就是说我们并不是直接优化转移，而是考虑式子的组合意义，设了个新状态。

原因是一个最优策略下的期望值 ≠ 对所有可能情况取平均的期望值，

可以用如下程序验证：

#include <bits/stdc++.h>
using namespace std;

int main() {
    cout << fixed << setprecision(10);

    int N, C;
    cin >> N >> C;

    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    sort(A.begin(), A.end(), greater());

    vector<double> f(1 << N);
    f[0] = 0;
    for (unsigned k = 1; k <= N; k++) {
        for (unsigned s = 0; s < 1 << N; s++) {
            if (popcount(s) != k) continue;
            for (unsigned bit = 0; bit < N; bit++) {
                if (s >> bit & 1) {
                    f[s] += max<double>(A[bit], f[s ^ (1 << bit)]) / k;
                }
            }
            f[s] -= C;
        }
    }
    cout << f.back() << endl;

    vector g(N + 1, vector<double>(N + 1));
    for (int k = 1; k <= N; k++) {
        double sum = 0;
        for (int j = 1; j <= k; j++) {
            sum += max<double>(A[j - 1], g[k - 1][j - 1]);
            g[k][j] = -C + 1.0 * (k - j) / k * g[k - 1][j] + sum / k;
            double maxx = -0x3f3f3f3f3f3f3f3f;
            cerr << "k = " << k << ", j = " << j << "   ";
            for (unsigned s = 0; s < 1 << N; s++) {
                if (popcount(s) != k) {
                    continue;
                }
                if ((s & ((1 << j) - 1)) != ((1 << j) - 1)) {  
                    continue;
                }
                if (s >> j & 1) {
                    continue;
                }
                maxx = max(maxx, f[s]);
            }
            cerr << maxx << " " << g[k][j] << endl;
        }
    }
    cout << g[N][N] << endl;    
 
    return 0;
}

Node 3

继续考虑组合意义，上面的方程还是有浪费。

我们的策略一定是对于还剩 $k$ 张牌的时候，我们会设定一个阈值 $j$，如果抽到的牌是全局前 $j$ 大，那么直接结束，否则继续抽取。如果令 $f(k)$ 表示还剩 $k$ 张牌的最大期望，那么直接枚举这个阈值 $j$，就有转移

$$f(k) = - C + \max_{j=1}^{k} \bigg\lbrace \frac{k - j}{k} \times f(k-1) + \frac{1}{k} \sum_{i=1}^j A_{i} \bigg\rbrace$$

感性地考虑，如果抽到一张好牌就直接结束了，否则抽到一张烂牌继续游戏，$k$ 减少。在 $k$ 减小的过程中，我们扔掉的都是分数较低的牌，期望抽到的排名就更低。或者这样考虑，多抽几次肯定是为了抽到更好的。设决策点为 $j_{k}$，这些 $j_{k}$ 一定单调不降，即 $j_{0} \leqslant j_{1} \leqslant \dots \leqslant j_{N}$。

转移方程具有决策单调性，可以双指针维护 $j$，做到 $\mathcal{O}(N)$。

#include <bits/stdc++.h>
using namespace std;

int main() {
    cout << fixed << setprecision(10);

    int N, C;
    cin >> N >> C;

    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    sort(A.begin(), A.end(), greater());

    vector<long double> f(N + 1);
    long double pre = 0;
    for (int k = 1, j = 0; k <= N; k++) {
        while (j < k && A[j] > f[k - 1]) {
            pre += A[j++];
        }
        f[k] = -C + 1.0 * (k - j) / k * f[k - 1] + pre / k;
    }
    cout << f[N] << endl; 
 
    return 0;
}

Node 4

我们的总策略有三个贪心：

1. 如果已经扔掉了排名为 $j$ 的牌，在之后的抽取中，一定会扔掉排名为 $j+1,j+2,\dots$ 的牌；
2. 如果某一轮的策略是抽到排名为 $j$ 的牌就结束游戏，那么在这一轮中，抽到排名为 $j-1,j-2,\dots$ 的牌也一定结束游戏，也即每轮有一个阈值；
3. 如果某一轮的阈值是 $j$，那么在之后的抽取中，阈值只会比 $j$ 更小，希望抽到排名更靠前的牌。

这几个贪心看起来都很显然。。

第一个贪心启发我们只考虑极长的未被抽取的前缀，第二个贪心保证确定 $j$ 之后的转移是确定的、无需做决策的。这便得到只包含一个 $\max$ 的转移方程。

而第三个贪心指出这个转移方程具有决策单调性，无需一一比较每项的 $\max$，直接考虑是否移动最优决策点即可。

杜老师题解

首先把所有数从大到小排序。我们的策略一定是对于第一轮，我们会设定一个阈值 $t_1$，如果抽到的牌是全局前 $t_1$ 大，那么直接结束，否则继续抽取。对于第二轮，我们继续会设定一个阈值 $t_2$，后续轮次依次类推。这些阈值的设定与抽到了什么牌无关，并且是单调不增的，也就是 $t_1 \geq t_2 \geq \dots \geq t_n$。

一个比较符合直觉的的理解为：如果抽了 $k$ 轮还没结束，意味着前面抽的牌的排名都是大于 $t_k$。从后面的轮次来看，再抽到这些牌也会继续，所以都是垃圾牌，也就意味着后面的策略和具体抽了哪些牌无关。并且到后面的轮次还没结束，意味着我们前面扔掉了一些垃圾牌，那么剩下的牌会更偏向于好牌，所以阈值会相应的提高。

严谨一点的证明再说。

这样可以得到一个 $O(n^2)$ 的 $dp$，即令 $dp[i][j]$ 表示还剩 $i$ 张牌，当前极长没有被选中的前缀为 $j$ 的最大期望收益。那么有转移

$$dp[i][j] = \frac{i-j}{i} \times dp[i-1][j] + \frac{1}{i} \sum_{k=1}^j \max(dp[i-1][k-1], a_k) - c$$

含义为如果选中的不是前 $j$ 个，之前已经扔掉了 $j+1$，那么这个一定会扔掉，否则考虑扔掉继续做或者直接选择 $a_k$。

对着这个式子直接优化是困难的。继续考虑组合意义，根据前面的假设，在最优策略下，如果剩下 $i$ 张牌，那么这些牌一定是一个前缀加上垃圾牌，那么这个时候的最大期望收益和前面抽了什么牌没有关系，所以可以等效为剩下前 $i$ 大的。

令 $dp[i]$ 表示还剩前 $i$ 大的牌的最大期望。考虑当前的决策为如果抽到前 $j$ 大的就停止，否则继续抽。那么有转移

$$dp[i] = \max_{j=1}^i \frac{\sum_{k=1}^j a_k + dp[i-1] \times (i - j)}{i} - c$$

也就是选 $a_j\geq dp[i-1]$ 的最大位置即可，这也是倒数第 $i$ 轮对应的阈值。

dp 可以用单调性做到 $O(n)$。

野羊 Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const ll N = 2e5 + 10;

ld a[N], b[N];
ld f[N];

void eachT()
{
    int n, c;
    cin >> n >> c;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    sort(a + 1, a + n + 1, greater<>());

    f[1] = a[1] - c;
    ll sum = a[1];
    for (int i = 2, j = 1; i <= n; i++)
    {
        while (j < i && f[i - 1] < a[j + 1])
        {
            j++;
            sum += a[j];    
        }
        f[i] = (sum + f[i - 1] * (i - j)) / i - c;
    }
    cout << f[n] << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(15);
    int t = 1;
    while (t--)
    {
        eachT();
    }
}