敵を殺すための武器で最小の動きを見つけるためのC++コード

n個の要素を持つ配列Aがあり、別の数Hがあるとします。Hは敵の体力です。n個の武器があり、i番目の武器のダメージ力はA[i]です。さまざまな武器を使用して敵を殺すことができます。同じ武器を2回続けて使用することはできません。敵を殺すために武器を使用できる最小回数を数える必要があります。

したがって、入力がA =[2、1、7]のような場合; H =11の場合、出力は3になります。これは、ダメージパワーが7の武器を使用する場合、2を使用し、次に7を使用すると、敵を倒すことができるためです。

ステップ

これを解決するには、次の手順に従います-

sort the array A
n := size of A
x := (A[n - 1] + A[n - 2])
return H / x * 2 + (H mod x + A[n - 1] - 1) / A[n-1]

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A, int H){
   sort(A.begin(), A.end());
   int n = A.size();
   int x = (A[n - 1] + A[n - 2]);
   return H / x * 2 + (H % x + A[n - 1] - 1) / A[n - 1];
}
int main(){
   vector<int> A = { 2, 1, 7 };
   int H = 11;
   cout << solve(A, H) << endl;
}

入力

{ 2, 1, 7 }, 11

出力

3