Baseball

题目描述

你得到一个长度为 $N$ 的序列 $P=(P_1,P_2,\dots,P_N)$。Takahashi 和 Aoki 将使用序列 $P$ 进行一个游戏。 首先，Takahashi 将从 $1,2,\dots,N$ 中选择 $K$ 个互不相同的整数 $x_1,x_2,\dots,x_K$。 接着，Aoki 将以与 $P_y$ 成正比的概率从 $1,2,\dots,N$ 中选择一个整数 $y$。也就是说，选中整数 $y$ 的概率为 $\dfrac{P_y}{\sum_{y'=1}^N P_{y'}}$。然后，Aoki 的得分将是 $\displaystyle \min_{i=1,2,\dots,K} |x_i-y|$。 Takahashi 想要最小化 Aoki 得分的期望值。求当 Takahashi 选择 $x_1,x_2,\dots,x_K$ 使该期望值最小时，该期望值乘以 $\sum_{y'=1}^N P_{y'}$ 的值。保证需输出的值为整数。

输入格式

输入从标准输入给出，格式如下： $N$ $K$ $P_1$ $P_2$ $\dots$ $P_N$

输出格式

输出答案。

5 2
1 1 1 1 1

3

5 1
0 0 1 0 0

0

1 1
100

0

20 7
4262 9522 2426 3823 7364 964 2743 2423 1955 5274 3684 847 363 35 278 3220 203 2904 6304 1928

22809

提示

$1 \leq N \leq 5 \times 10^4$ $1 \leq K \leq N$ $0 \leq P_i \leq 10^5$ $1 \leq \sum_{y'=1}^N P_{y'} \leq 10^5$ 所有输入值均为整数。Aoki 选择 $1,2,\dots,N$ 的概率都相等：$\frac{1}{5}$。 如果 Takahashi 选择 $x_1=2$ 和 $x_2=4$，那么 Aoki 得分的期望值为 $1 \times \frac{1}{5} + 0 \times \frac{1}{5} + 1 \times \frac{1}{5} + 0 \times \frac{1}{5} + 1 \times \frac{1}{5} = \frac{3}{5}$。 如果 Takahashi 选择 $x_1=2$ 和 $x_2=3$，那么 Aoki 得分的期望值为 $1 \times \frac{1}{5} + 0 \times \frac{1}{5} + 0 \times \frac{1}{5} + 1 \times \frac{1}{5} + 2 \times \frac{1}{5} = \frac{4}{5}$。 无论 Takahashi 如何选择，Aoki 得分的期望值都不可能小于 $\frac{3}{5}$。因此最小值为 $\frac{3}{5}$，将该值乘以 $5$ 后应输出 $3$。

标签: AtCoder|abc355G

来源

AtCoder|abc355G