← 返回题目列表

AtCoder · tkppc4_2_h

H. 按键大战

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

配点: 700 点

問題文

PA实验室目前流行一款名为“按键大战”的游戏。在 PA 实验室 N 有几名成员,其中一名成员参加了一场名为“按键大战”的比赛。 K (2K \leq N) 我们决定派出一名代表球员。
每个成员都有一个固定值,称为“密钥功率”,并且每个成员 i 的击键力度为 A_i ,并且不存在具有相同值的成员对。
目前,在 PA 实验室,我们专注于“键控能力”。小来自 K 某人已被选为“代表候选人”。

作为队伍的队长,您必须执行以下操作。 执行此操作至少 0 次。

  • 当时作为代表候选人的成员 i,非代表候选人的会员 自由选择 j 并与他们对战。
  • 部員 i 是概率 \frac{A_i}{A_i+A_j} 获胜,俱乐部会员 使用 j 是概率 \frac{A_j}{A_i+A_j} 获胜。 如果
  • 当时作为代表候选人的成员 i 获胜,则不会发生任何事情。
  • 当时非代表候选人的会员 如果 j 获胜,则成员 j 为新代表候选人,俱乐部会员 i 被排除在代表候选人之外。

一旦停止让他们参加比赛,国家队候选成员将成为代表球员。
您希望通过参加尽可能少的比赛来最大化代表性玩家的击键力量总和。如果将预期的比赛次数最小化,则需要进行多少场比赛才能使代表玩家的击键能力之和最大化?求其期望值。

制約

  • 所有输入均为整数。
  • 2 \leq N \leq 10^5
  • 1 \leq 2K \leq N
  • 1 \leq A_i \leq 10^9
  • A_i \neq A_j(i \neq j)

入力

输入是按以下格式从标准输入给出的。

N K
A_1 A_2 ... A_{N-1} A_N

出力

请输出匹配次数的最小期望值。
如果绝对或相对误差为 如果在 10^{-9} 之内,则正确。


入力例1

2 1
42 8

出力例1

1.190476190476

部員 1 和成员 2 ,成员 1 别无选择,只能继续互相对战,直到获胜。
此时匹配次数的期望值为 \frac{25}{21} = 1.190476... 次。

入力例2

5 1
3 9 4 2 8

出力例2

1.222222222222

入力例3

10 5
20 3 9 5 8 1 100 32 7 2

出力例3

5.723472222222

作者: TAISA_