AtCoder Beginner Contest #085
問題文
敵が $1$ 匹いて,その敵のHPは $H$ である.
こちらは $N$ 個の刀を持っていて,刀 $i$ で攻撃する際,以下の $2$ 種類の攻撃方法が取れる:
敵を倒す (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$ と攻撃方法を採用した場合の攻撃回数を求めて,その最小値を取るほうが書きやすい気がする (以下のコードはこの方針).
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月26日06時16分54秒
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)