AT_abc355_g [ABC355G] Baseball

题目描述

给定一个长度为 $N$ 的数列 $P=(P_1,P_2,\dots,P_N)$。高桥君和青木君将使用数列 $P$ 进行一场游戏。

首先，高桥君从 $1,2,\dots,N$ 中选择 $K$ 个互不相同的整数 $x_1,x_2,\dots,x_K$。

接着，青木君从 $1,2,\dots,N$ 中以与 $P_y$ 成正比的概率选择一个整数 $y$。也就是说，整数 $y$ 被选中的概率为 $\dfrac{P_y}{\sum_{y'=1}^N P_{y'}}$。然后，青木君获得分数 $\displaystyle\min_{i=1,2,\dots,K} |x_i-y|$。

高桥君希望最小化青木君所能获得分数的期望值。请你求出当高桥君适当选择 $x_1,x_2,\dots,x_K$ 时，青木君能获得的分数期望值的最小值，并将其乘以 $\sum_{y'=1}^N P_{y'}$ 后输出。可以证明，输出的结果一定是整数。

输入格式

输入以如下格式从标准输入读入。

$N$ $K$ $P_1$ $P_2$ $\dots$ $P_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

5 2
1 1 1 1 1

输出 #1

3

输入输出样例 #2

输入 #2

5 1
0 0 1 0 0

输出 #2

0

输入输出样例 #3

输入 #3

1 1
100

输出 #3

0

输入输出样例 #4

输入 #4

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

输出 #4

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$
• 所有输入均为整数

样例解释 1

青木君选择 $1,2,\dots,N$ 的概率都是 $\frac{1}{5}$。如果高桥君选择 $x_1=2,x_2=4$，则青木君获得的分数期望为 $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}$。如果高桥君选择 $x_1=2,x_2=3$，则青木君获得的分数期望为 $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}$。无论高桥君如何选择，青木君获得的分数期望都不会小于 $\frac{3}{5}$。因此最小值为 $\frac{3}{5}$，将其乘以 $5$，输出 $3$。

由 ChatGPT 4.1 翻译