मान लीजिए हम एक वीडियो गेम खेल रहे हैं जहाँ नायक चाकू से दुश्मनों को हराता है। नायक चाकू से दुश्मन पर वार कर सकता है या उसे फेंक सकता है। यदि नायक चाकू फेंकता है, तो उसे वापस नहीं पाया जा सकता। चाकू i द्वारा पहुँचाई गई क्षति 'knives' सरणी में दी गई है जहाँ प्रत्येक तत्व {slash, throw} प्रारूप में है। 'Slash' का अर्थ है उस चाकू से वार करके पहुँचाई गई क्षति और 'throw' का अर्थ है उस चाकू को फेंककर पहुँचाई गई क्षति। वार असीमित बार किया जा सकता है, लेकिन एक चाकू केवल एक बार फेंका जा सकता है। अब एक दुश्मन प्रकट होता है जिसका स्वास्थ्य h है। हमें दुश्मन को हराने के लिए आवश्यक न्यूनतम ऑपरेशन्स (वार या फेंक) की संख्या ज्ञात करनी है। दुश्मन तब हारता है जब उसका स्वास्थ्य 0 हो जाता है।
उदाहरण के लिए, यदि इनपुट है n = 2, h = 11, knives = {{4, 5}, {3, 6}}, तो आउटपुट 2 होगा।
यदि नायक दोनों चाकू फेंकता है, तो पहुँचाई गई क्षति 5 + 6 = 11 होगी। दुश्मन का स्वास्थ्य 0 हो जाता है, इसलिए वह हार जाता है।
चरण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
val := 0
i := 0 से n-1 तक:
val := max(val, knives[i] का पहला मान)
knives सरणी को सॉर्ट करें
res := 0
i := 0 से n-1 तक:
यदि knives[i] का दूसरा मान > val, तो:
h := h - knives[i] का दूसरा मान
res बढ़ाएँ
यदि h <= 0, तो:
res प्रिंट करें
बाहर निकलें
अन्यथा:
लूप से बाहर निकलें
res + ceil(h / (double)val) प्रिंट करें
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#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
