← 返回题目列表

AtCoder · abc355_g

G. 棒球

中文机器翻译题面 查看原题

分数: 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