自动搬运

查看原文

来自洛谷，原作者为

	Falashiro 丝之歌什么时候出

搬运于2025-08-24 23:07:38，当前版本为作者最后更新于2024-12-24 00:07:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

设 $f_{i,j}$ 表示剩余 $i$ 次获取点位的机会，当前点位最小跑动距离为 $a_j$ 时最后跑动距离的期望的最小值，设 $g_i=\sum\limits_{j=1}^mp_j\times f_{i,j}$。易知 $f_{0,i}=a_i$。

当 $i>0$ 时，有：

$$\begin{aligned} f_{i,j}&=\min\{a_j,\sum\limits_{k=1}^mp_k\times f_{i-1,k}\}\\ &=\min\{a_j,g_{i-1}\} \end{aligned} $$

我们可以将 $a$ 序列从小到大排序，则存在整数 $k\in[1,m]$，使得：

$$f_{i,j}= \left\{ \begin{aligned} a_j\ (j\le k)\\ g_{i-1}\ (j>k) \end{aligned} \right. $$

于是有：

$$\begin{aligned} g_i&=\sum\limits_{j=1}^mp_j\times f_{i,j}\\ &=(\sum\limits_{j=1}^kp_j\times a_j)+(\sum\limits_{j=k+1}^mp_j)\times g_{i-1} \end{aligned} $$

设 $s_i=\sum_{j=1}^ip_j$，$w_i=\sum_{j=1}^ip_j\times a_j$，则：

$$\begin{aligned} g_i=w_k+(1-s_k)\times g_{i-1} \end{aligned} $$

即：

$$\begin{pmatrix} g_{i}\\ 1 \end{pmatrix} = \begin{pmatrix} 1-s_k&w_k\\ 0&1 \end{pmatrix} \begin{pmatrix} g_{i-1}\\ 1 \end{pmatrix} $$

显然随着 $i$ 的增加，$g_i$ 单调不增，$k$ 单调不增，那么 $k$ 至多变化 $m-1$ 次。

对于 $k$ 相同的一段，我们可以通过矩阵快速幂以 $\Theta(\log n)$ 的时间复杂度求出一个 $g$ 的值，结合倍增，则能够以 $\Theta(\log n)$ 的时间复杂度求出最小的满足 $g_i<a_k$ 的 $i$，即下一个 $k$ 变化的分界点。而 $k$ 至多变化 $m-1$ 次，于是我们可以以 $\Theta(m\log n)$ 的时间复杂度求出 $g_n$，$g_n$ 即为最终答案。