[AtCoder] ABC 173 D – Chat in a Circle
問題
方針
証明をしないとダメだと思いますが、貪欲法で考えます。\( 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; }
ディスカッション
コメント一覧
まだ、コメントがありません