[AtCoder] ABC 173 D – Chat in a Circle

2020年12月14日

問題

方針

証明をしないとダメだと思いますが、貪欲法で考えます。\( 2 \) 人目以降の到着で心地よさが増えることと、心地よさの増分は一人分だけであることを考慮して、その時々で心地よさを最大化します。まず初めに、配列を降順に並び替え、\( A_0 \) が到着したとします。次に、\( A_1, A_2, … \) と順番に到着すると、心地よさの和は、

\[A_0 + A_1 + A_1 + A_2 + A_2 + A_3 + A_3 + \cdots\]

となります。

コード

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