分数: 650 点
问题陈述
给你一个序列 P=(P_1,P_2,\dots,P_N) 长度 N。高桥和青木将使用该序列玩游戏 P.
首先,高桥会选择 K 不同的整数 x_1,x_2,\dots,x_K 来自 1,2,\dots,N.
接下来,青木将选择一个整数 y 来自 1,2,\dots,N 的概率与 P_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'}。保证要打印的值是整数。
约束
- 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
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N K P_1 P_2 \dots P_N
输出
打印答案。
示例输入 1
5 2 1 1 1 1 1
示例输出 1
3
青木选择的概率 1,2,\dots,N 全部相等: \frac{1}{5}.
如果高桥选择 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}.
如果高桥选择 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}.
无论高桥如何选择,青木得分的期望值都不能小于 \frac{3}{5}。因此,最小值为 \frac{3}{5},因此打印该值乘以 5,即 3.
示例输入 2
5 1 0 0 1 0 0
示例输出 2
0
示例输入 3
1 1 100
示例输出 3
0
示例输入 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