ABC138 C - Alchemist

問題はこちら
atcoder.jp

方針

「最後に残る具材の価値を最大にしたい」ということは，「 回目の操作で最も価値の大きい2つを鍋に投入したい」ということです。
鍋に入れられた具材の影響力は回数を経るごとに で割られて小さくなっていくので，価値の小さい具材から鍋に入れていけばいいです。

コード中では， 回目の操作のみint型同士の計算になるので，double型に変換して小数点以下が出るようにしています（もともと をdouble型で宣言すれば済む話ですが，どっちの方が綺麗なコードなんでしょうか）。

コード

#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int n;
    cin>>n;
 
    vector<int> v(n);
    vector<double> d(n-1);
 
    for(int i=0; i<n; i++){
        cin>>v[i];
    }
 
    sort(v.begin(),v.end());
 
    d[0]=((double)v[0]+(double)v[1])/2;
 
    for(int i=1; i<n-1; i++){
        d[i]=(d[i-1]+v[i+1])/2;
    }
 
    cout<<d[n-2]<<endl;
}