सी ++ प्रोग्राम दुश्मन को हराने के लिए आवश्यक न्यूनतम संख्या में संचालन का पता लगाने के लिए

मान लीजिए, हम एक वीडियो गेम खेल रहे हैं जहां नायक अपने दुश्मनों को हराने के लिए चाकू का उपयोग करता है। नायक चाकू का उपयोग दुश्मन को मारने के लिए कर सकता है या वह इसे दुश्मन की ओर फेंक सकता है। यदि नायक चाकू फेंकता है, तो उसे फिर से प्राप्त नहीं किया जा सकता है। चाकू i द्वारा किए गए नुकसान को 'चाकू' सरणी में दिया गया है जहां प्रत्येक तत्व {स्लैश, थ्रो} के रूप में है। 'स्लैश' का अर्थ है किसी दुश्मन को उस चाकू से काटकर जो नुकसान हुआ है और 'फेंक' का अर्थ है उस विशेष चाकू को फेंकने से उन्हें हुई क्षति। स्लैशिंग असीमित बार की जा सकती है, लेकिन चाकू केवल एक बार फेंका जा सकता है। अब, एक शत्रु प्रकट होता है जिसका स्वास्थ्य ज है। हमें दुश्मन को हराने के लिए आवश्यक न्यूनतम संख्या में ऑपरेशन (स्लैशिंग या थ्रोइंग) का पता लगाना होगा। 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