[AtCoder] ABC 138 C – Alchemist

2019年8月19日

問題

方針

食材の価値

\( 1 \) 回の合成で使用された食材の価値は半減します。食材 \( i \) が合成に使われた回数を \( a_i \) とし、最終的な価値を \( f \) とすると、

\[f = \dfrac{v_1}{2^{a_1}} + \dfrac{v_2}{2^{a_2}} + \cdots +\dfrac{v_N}{2^{a_N}} \]

となります。価値の大きいものの合成回数が増えると \( f \) の値が小さくなるので、価値が低い食材を合成に多く使われた方が良いです。例えば、\( N = 4 \) のとき、\( v_i \leq v_{i+1} \) のように昇順に整列されているとすると、

\[
\begin{eqnarray}
\dfrac{v_1 + v_2 + v_3 + v_4}{4} &\leq& \dfrac{v_1 + v_2}{8} + \dfrac{v_3}{4} + \dfrac{v_4}{2}\\
\dfrac{2v_1 + 2v_2 + 2v_3 + 2v_4}{8} &\leq& \dfrac{v_1 + v_2 + 2v_3 + 4v_4}{8}
\end{eqnarray}
\]

となることが分かります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  int N;
  cin >> N;
  vector<double> v(N);
  for (int i = 0; i < N; i++) {
    cin >> v[i];
  }
  sort(v.begin(), v.end());
  double ans = (v[0] + v[1]) / pow(2.0, N - 1);
  for (int i = 2; i < N; i++) {
    ans += v[i] / pow(2.0, N - i);
  }
  cout << ans << "\n";
  return 0;
}