[ABC003C] AtCoderプログラミング講座

【题意】 初始时 $C=0$ ，给出一个含 $n$ 个数的序列 $\{R\}$，取其中任意 $k$ 个数的排列 $R_1,R_2,\cdots R_k$，并依次运算 $C=(C+R_i)/2$ .你的任务是使得最终的 $C$ 尽可能大。 【输入格式】 第一行，$n,k$； 接下来一行 $n$ 个数，表示序列 $\{R\}$。 【输出格式】 一行一个数 $C$，误差不超过 $10^{-6}$（小数点后 $6$ 位） translated by @Forward_Star

[problemUrl]: https://atcoder.jp/contests/abc003/tasks/abc003_3 AtCoder社では、優秀な競技プログラマーの講座動画を $ N $ 個配信しています。 初心者競技プログラマーの高橋くんは、AtCoder社が配信している動画を見て修練しようとしています。 高橋くんの実力はレートという実数値で表され、レートが高いほど実力が高いことを表します。 高橋くんのレートが $ C $ の時に、レート $ R $ の競技プログラマーの講座動画を見ると、高橋くんのレートは $ (C+R)/2 $ に変化します。 高橋くんは、講座動画を合計で $ K $ 個まで好きな順番で見ることができますが、同じ競技プログラマーの講座動画は一度までしか見ることができません。 講座動画を配信している $ N $ 人のレートが与えられた時、高橋くんが講座動画を見ることによって達成できるレートの最大値を求めるプログラムを書いてください。 ただし、高橋くんの初期レートは $ 0 $ です。 入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ R_1 $ $ R_2 $ ... $ R_N $ 1. $ 1 $ 行目には、講座動画の数を表す整数 $ N\ (1\ ≦\ N\ ≦\ 100) $ と高橋くんが見ることのできる動画の数を表す整数 $ K\ (1\ ≦\ K\ ≦\ N) $ がスペース区切りで与えられる。 2. $ 2 $ 行目には、講座動画を配信している競技プログラマーのレートを表す整数 $ R_i\ (1\ ≦\ R_i\ ≦\ 4,000) $ がスペース区切りで与えられる。 高橋くんが達成できる最大レートを $ 1 $ 行で出力せよ。 絶対誤差、または、相対誤差が $ 10^{-6} $ 以下であれば許容される。 また、出力の末尾には改行を入れること。 ``` <pre class="prettyprint linenums"> 2 2 1000 1500 ``` ``` <pre class="prettyprint linenums"> 1000.000000 ``` - 以下の方法が最適です。 - まず、レート $ 1000 $ の競技プログラマーの講座動画を見ます。これにより、高橋くんはレート $ 0 $ から $ (0+1000)/2\ =\ 500 $ になります。 - 次に、レート $ 1500 $ の競技プログラマーの講座動画を見ます。これにより、高橋くんはレート $ 500 $ から $ (500+1500)/2\ =\ 1000 $ になります。 - しかし、例えば、以下の方法は最適ではありません。 - まず、レート $ 1500 $ の競技プログラマーの講座動画を見ます。これにより、高橋くんはレート $ 0 $ から $ (0+1500)/2\ =\ 750 $ になります。 - 次に、レート $ 1000 $ の競技プログラマーの講座動画を見ます。これにより、高橋くんはレート $ 750 $ から $ (750+1000)/2\ =\ 875 $ になります。 ``` <pre class="prettyprint linenums"> 2 1 1000 1500 ``` ``` <pre class="prettyprint linenums"> 750 ``` - このケースでは高橋くんは $ 1 $ 個の講座動画しか見ることができません。 - レート $ 1500 $ の競技プログラマーの講座動画を見るのが最適です。 ``` <pre class="prettyprint linenums"> 10 5 2604 2281 3204 2264 2200 2650 2229 2461 2439 2211 ``` ``` <pre class="prettyprint linenums"> 2820.031250000 ```