โปรแกรม C++ เพื่อค้นหาจำนวนปฏิบัติการขั้นต่ำที่จำเป็นในการเอาชนะศัตรู

สมมุติว่าเรากำลังเล่นวิดีโอเกมที่ตัวเอกใช้มีดเพื่อเอาชนะศัตรูของเขา ตัวเอกสามารถใช้มีดฟันศัตรูหรือจะขว้างไปทางศัตรูก็ได้ ถ้าตัวเอกขว้างมีดออกไป จะไม่สามารถดึงกลับมาได้อีก ความเสียหายที่เกิดจากมีด i จะได้รับใน 'มีด' อาร์เรย์ โดยที่แต่ละองค์ประกอบอยู่ในรูปแบบ {slash, throw} 'ฟัน' หมายถึงความเสียหายที่ทำกับศัตรูโดยการฟันพวกเขาด้วยมีดนั้นและ 'ขว้าง' หมายถึงความเสียหายที่ทำกับพวกเขาโดยการขว้างมีดนั้น การฟันสามารถทำได้ไม่จำกัดครั้ง แต่สามารถขว้างมีดได้เพียงครั้งเดียวเท่านั้น ตอนนี้ ศัตรูที่มีพลังชีวิตปรากฏ h. เราต้องหาจำนวนปฏิบัติการขั้นต่ำ (การฟันหรือการขว้างปา) ที่จำเป็นต่อการเอาชนะศัตรู ศัตรูจะพ่ายแพ้เมื่อมีเลือดเหลือ 0

ดังนั้น หากอินพุตเป็น n =2, h =11, knives ={{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