Hide

Problem A
木材の裁断

ヤラグラックは最近、木材の裁断ビジネスに参入し、今では木材の裁断を希望する$N$人の顧客がいます。 サイズ$s$の木材をカットするには$s$の時間が必要で、ヤラグラックは一度に一本の木材しかカットできません。 お客様の幸せを最大化するために、ヤラグラックは、お客様がすべての木材をカットしてもらうまでに待つ 平均的な合計時間を最小限にしたいと考えています。彼を助けてあげてください。

入力

最初の行には、テストケースの数を示す単一の整数$T \leq 10$が含まれています。 各テストケースは、顧客の数である整数 $N$ ($1 \leq N \leq 10^5$) で始まります。続く$N$行のうち、$i$行目は顧客$i$がカットしてもらいたい木片の数を表す整数$W_ i$ ($1 1 \leq W_ i \leq 10^5$)で始まり、続く$W_ i$個の整数がそれぞれの木片の大きさを表します。それぞれの木片のサイズは、$1$から$1\, 000$までの間です。木片の総数は$10^5$を超えません。

出力

各テストケースについて、顧客がすべての木片をカットするまでに待つ最小の平均合計時間を含む1行を出力してください。答えは、絶対誤差や相対誤差が $10^{-6}$ を超えなければ正解とみなされます。

サンプル入力 1 サンプル出力 1
2
1
2 7 5
2
1 7
1 5
12.0000000000
8.5000000000

Please log in to submit a solution to this problem

Log in