敵を倒すために必要な操作の最小数を見つけるためのC++プログラム

主人公がナイフを使って敵を倒すビデオゲームをプレイしているとします。主人公はナイフを使って敵を斬ったり、敵に向かって投げたりすることができます。主人公がナイフを投げた場合、それを再び取得することはできません。ナイフiによって与えられるダメージは、各要素が{slash、throw}の形式である配列'knives'で与えられます。 「スラッシュ」とは、そのナイフで敵を斬ることによって敵に与えられるダメージを意味し、「投げる」とは、その特定のナイフを投げることによって敵に与えられるダメージを意味します。斬撃は無制限に行うことができますが、ナイフは一度しか投げることができません。さて、体力hの敵が現れます。敵を倒すために必要な最小限の操作（斬撃または投擲）を見つける必要があります。体力が0の場合、敵は敗北します。

したがって、入力がn =2、h =11、ナイフ={{4、5}、{3、6}}の場合、出力は2になります。

主人公が両方のナイフを投げた場合、与えられるダメージは5 + 6 =11です。敵の体力が0になるため、敵は敗北します。

ステップ

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

val := 0
for initialize i := 0, when i < n, update (increase i by 1), do:
   val := maximum of (val and first value of knives[i])
sort the array knives
res := 0
for initialize i := 0, when i < n, update (increase i by 1), do:
   if second value of knives[i] > val, then:
      h := h - second value of knives[i]
      (increase res by 1)
      if h <= 0, then:
         print(res)
   exit
      Otherwise
Come out from the loop
print((res + ceiling value of (h / (double))))

例

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

#include <bits/stdc++.h>
using namespace std;

void solve(int n, int h, vector<pair<int, int>> knives){
   int val = 0;
   for(int i = 0; i < n; i++){
      val = max(val, knives[i].first);
   }
   sort(knives.begin(), knives.end());
   int res = 0;
   for(int i = 0; i < n; i++){
      if(knives[i].second > val){
         h -= knives[i].second;
         res++;
         if(h <= 0){
            cout << res << endl;
            return;
         }
      }
      else break;
   }
   cout << (res + ceil(h / (double)val)) << endl;
}
int main() {
   int n = 2, h = 11;
   vector<pair<int, int>> knives = {{4, 5}, {3, 6}};
   solve(n, h, knives);
   return 0;
}

入力

2, 11, {{4, 5}, {3, 6}}

出力

2