AtCoder Beginner Contest #085 D問題 - Katana Thrower

Source

AtCoder Beginner Contest #085
問題文

問題概要

敵が $1$ 匹いて，その敵のHPは $H$ である．
こちらは $N$ 個の刀を持っていて，刀 $i$ で攻撃する際，以下の $2$ 種類の攻撃方法が取れる：

  1. 刀 $i$ を振ると敵に $A_i$ のダメージを与える．何回でも利用可能
  2. 刀 $i$ を投げると敵に $B_i$ のダメージを与える．以降刀 $i$ は利用できなくなる

敵を倒す (HPを $0$ 以下にする) のに必要な最小攻撃回数を求める問題．

解法

攻撃の順番を変えても合計ダメージは変わらないので，刀を投げるのは後回しにする．
すると，結局，刀を振るのは何回でも利用可能で，刀を投げるのはそれぞれ $1$ 回のみ利用可能となる．
また，刀を振る際は，攻撃力の低い刀を利用する意味は無いので，刀を振るのは固定で $m = \max(A_i)$ のダメージとして良い．
よって，$\{B_k\}$ を大きい順にソートしておいて，$B_1, B_2, \ldots, B_i, m, m, m, \ldots$ (ただし，$B_i \geq m \geq B_{i+1}$) の順番で攻撃方法を採用していけば良い．
適切に実装すれば時間計算量 $O(N \log N)$ 程度で解ける．
実際には，全ての $i$ に対して $B_1, B_2, \ldots, B_i, m, m, m, \ldots$ と攻撃方法を採用した場合の攻撃回数を求めて，その最小値を取るほうが書きやすい気がする (以下のコードはこの方針)．

cLay（version 20180107-1）のコード

C++に変換後のコードはこちら

int N, H, A[100000], B[100000];
{
  int i, mx;
  int res;
  
  rd(N,H,(A,B)(N));
  mx = max(A(N));
  sort(B,B+N);

  res = H /+ mx;
  rep(i,N){
    H -= B[N-i-1];
    if(H <= 0){
      res <?= i+1;
      break;
    }
    res <?= i+1 + (H /+ mx);
  }

  wt(res);
}

Current time: 2024年04月16日13時26分47秒
Last modified: 2018年01月07日23時04分13秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Beginner_Contest ABC085 ABC_D
トップページに戻る

Logged in as: unknown user (not login)

ログイン：