मान लीजिए हमारे पास n तत्वों की एक सरणी A है, और एक अन्य संख्या H है। H दुश्मन का स्वास्थ्य है। हमारे पास n हथियार हैं और iवें हथियार की हानिकारक शक्ति A[i] है। दुश्मन को मारने के लिए विभिन्न हथियारों का उपयोग किया जा सकता है। हम एक ही हथियार को लगातार दो बार उपयोग नहीं कर सकते। हमें दुश्मन को मारने के लिए हथियारों का उपयोग करने की न्यूनतम संख्या गिननी है।
उदाहरण के लिए, यदि इनपुट A = [2, 1, 7]; H = 11 है, तो आउटपुट 3 होगा, क्योंकि यदि हम 7 हानिकारक शक्ति वाले हथियार का उपयोग करते हैं, फिर 2 का उपयोग करते हैं, फिर फिर से 7 का उपयोग करते हैं तो हम दुश्मन को मार सकते हैं।
चरण
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
sort the array A n := size of A x := (A[n - 1] + A[n - 2]) return H / x * 2 + (H mod x + A[n - 1] - 1) / A[n-1]
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#includeusing namespace std; int solve(vector A, int H){ sort(A.begin(), A.end()); int n = A.size(); int x = (A[n - 1] + A[n - 2]); return H / x * 2 + (H % x + A[n - 1] - 1) / A[n - 1]; } int main(){ vector A = { 2, 1, 7 }; int H = 11; cout << solve(A, H) << endl; }
इनपुट
{ 2, 1, 7 }, 11आउटपुट
3