← 返回题目列表

AtCoder · scpc2026_div2_e

E. 打开魔法盒

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

表示言語

/ /

分数: 100 点

问题陈述

Lulu 发现了一个装有宝藏的魔法箱子。箱子上有 N 种不同的魔法,每种只施放一次,并且只能按正确顺序解除所有魔法才能打开。Lulu 是天才魔术师,已识别出箱子上的所有 N 魔法类型,但不知道必须解除它们的正确顺序。

为了打开盒子,露露尝试以下步骤。

  1. 露露从仍然施加在盒子上的法术中选择一个法术并尝试驱散它。 N 当露露尝试驱散第 i个法术时, M_i 魔力会被消耗。

  2. 如果尝试的法术在顺序上是正确的法术,驱散就会成功。如果顺序不正确,盒子会恢复到所有 N 法术都作用在其上的状态。露露可以立即知道驱散尝试是否成功。驱散法术所需的顺序不会改变。

  3. 一旦所有 N 法术被驱散,盒子就会打开。

鉴于 N 以及魔力消耗 M_i 每个法术,找出露露在使用最优策略打开盒子时预计消耗的魔力总量。正确的法术顺序是 N! 种可能顺序之一,且所有可能顺序的出现概率相等。

约束

  • 1 \leq N \leq 100\,000
  • 1 \leq M_i \leq 100\,000
  • 所有给定的数字都是整数。

输入

输入由标准输入按以下格式给出:

N
M_1 M_2 \dots M_N

输出

输出露露预计消耗的魔力总量。绝对误差或相对误差最多为 10^{-6} 已接受。


示例输入 1

1
10

示例输出 1

10

示例输入 2

2
10 20

示例输出 2

35

表示言語

/ /

分数: 100 点

문제

루루는 보물이 담긴 마법의 상자를 발견했다. 상자에는 서로 다른 N가지의 마법이 한 번씩 걸려 있으며, 이를 정확한 순서대로 모두 해제해야만 상자를 열 수 있다. 천재 마법사인 루루는 상자에 걸려 있는 N가지 마법의 종류는 전부 알아냈지만 해제해야 할 올바른 순서는 알지 못한다.

루루는 상자를 열기 위해 아래와 같은 방법으로 상자 열기를 시도한다.

  1. 루루는 N가지 마법 중 아직 상자에 걸려 있는 마법 하나를 선택하여 해제를 시도한다. i번째 마법을 해제 시도할 때 M_i의 마력이 소모된다.

  2. 만약 해제 시도한 마법이 순서에 맞는 마법이라면 해제에 성공한다. 순서에 맞지 않는 마법이라면 N가지 마법이 모두 걸린 상태로 되돌아간다. 해제 시도가 성공했는지 바로 알 수 있다. 해제하는 데 필요한 마법의 순서는 바뀌지 않는다.

  3. N개의 마법이 모두 해제되면 상자가 열린다.

N과 각 마법의 소모 마력 M_i가 주어질 때 루루가 최적의 전략으로 상자를 연다면 소모하게 될 마력 합의 기댓값을 구해 보자. 상자를 여는 올바른 마법의 순서는 N!가지 중 하나이며, 모든 가능한 순서가 올바른 순서일 확률은 동일하다.

제한

  • 1 \leq N \leq 100\,000
  • 1 \leq M_i \leq 100\,000
  • 입력으로 주어지는 수는 모두 정수이다.

입력

입력은 다음 형식으로 표준 입력으로 주어진다.

N
M_1 M_2 \dots M_N

출력

루루가 소모하게 될 마력 합의 기댓값을 출력한다. 절대/상대 오차는 10^{-6}까지 허용한다.


입력 예 1

1
10

출력 예 1

10

입력 예 2

2
10 20

출력 예 2

35