[AOJ] No. 0529 Darts
問題
方針
半分全列挙
ダーツは最大で \( 4 \) 本投げることができますが、そのすべての得点パターンを列挙することは厳しいと思います。なので、\( 2 \) 本投げた時に得られる \( M \) 以下の得点のパターンをすべて列挙します。得られた得点の配列を \( v \) とします。
次に、\( v \) を昇順に整列させます。全ての \( v \) の要素番号 \( i \) について、\( M – v[i] \) 以下の \( v \) の要素を二分探索します。二分探索によって得られた値を \( k \) とすると、最大値の候補は \( v[i] + k \) となります。
コード
提出したコード
二分探索
sort(v.begin(), v.end()); for (int i = 0; i < v.size(); i++) { int res = M - v[i]; if (res == 0) { ans = M; break; } int left = -1; int right = v.size(); while (right - left > 1) { int mid = (right + left) / 2; if (res >= v[mid]) left = mid; else right = mid; } ans = max(ans, v[i] + v[left]); }
ディスカッション
コメント一覧
まだ、コメントがありません