[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
```