Chương trình C ++ để tìm ra số lượng thao tác tối thiểu cần thiết để đánh bại kẻ thù

Giả sử, chúng ta đang chơi một trò chơi điện tử mà nhân vật chính dùng dao để hạ gục kẻ thù của mình. Nhân vật chính có thể sử dụng con dao để chém kẻ thù hoặc anh ta có thể ném nó về phía kẻ thù. Nếu nhân vật chính ném một con dao, nó sẽ không thể lấy lại được nữa. Sát thương do dao thứ i gây ra được cho trong mảng 'dao' trong đó mỗi phần tử có dạng {chém, ném}. 'Slash' có nghĩa là thiệt hại gây ra cho kẻ thù bằng cách chém họ bằng con dao đó và 'ném' có nghĩa là thiệt hại gây ra cho họ bằng cách ném con dao cụ thể đó. Chém có thể được thực hiện không giới hạn số lần, nhưng một con dao chỉ có thể được ném một lần. Bây giờ, một kẻ thù xuất hiện là người có sức khỏe h. Chúng ta phải tìm ra số lượng thao tác tối thiểu (chém hoặc ném) cần thiết để đánh bại kẻ thù. Kẻ thù bị đánh bại khi chúng còn 0 máu.

Vì vậy, nếu đầu vào là n =2, h =11, dao ={{4, 5}, {3, 6}}, thì đầu ra sẽ là 2.

Nếu nhân vật chính ném cả hai con dao, sát thương gây ra là 5 + 6 =11. Máu của kẻ địch trở thành 0, vì vậy chúng sẽ bị đánh bại.

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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))))

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
}

Đầu vào

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

Đầu ra

2