[AOJ] No. 0529 Darts

2019年5月18日

問題

方針

半分全列挙

ダーツは最大で \( 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]);
}