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$ と攻撃方法を採用した場合の攻撃回数を求めて,その最小値を取るほうが書きやすい気がする (以下のコードはこの方針).

cLayversion 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: 2021年09月19日20時07分42秒
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)

ログイン: