题解：P11469 校园跑

设 $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$ 时，有：

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

于是有：

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

即：

显然随着 $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$ 即为最终答案。