素材合成システム [yukicoder No.549]

https://yukicoder.me/problems/no/549

解説放送

https://youtu.be/3frI4o6H1d4?t=400

解説

https://yukicoder.me/submissions/192462

幾つか重要な考察がある

• 素材アンドロイドを合成されたアンドロイドとするのは無駄である (素材アンドロイドは非合成アンドロイドが最適)
• N - 1回の合成をするため、ある1つのアンドロイドは素材アンドロイドとなる必要が無い

以上の考察から、最大のアンドロイドに対し、他のアンドロイドを素材アンドロイドとして合成していくのが良いと分かる。
これをやると答え。

（もっともらしいことを書いているが、自分が解いたときは、★2だから適当な貪欲だろうと思ってやったら通っただけ）

int N, A[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    sort(A, A + N);
    
    int ans = 0;
    rep(i, 0, N - 1) ans += A[i] / 2;
    ans += A[N - 1];
    cout << ans << endl;
}