Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

सभी राक्षसों को मारने के लिए बम रखने के लिए न्यूनतम स्थानों की संख्या ढूंढने के लिए C++ प्रोग्राम


मान लीजिए हमारे पास दो ऐरे X और H हैं। दोनों N तत्वों के साथ हैं, साथ ही दो अन्य संख्याएं D और A हैं। एक कहानी पर विचार करें, एक चांदी की लोमड़ी N राक्षसों से लड़ रही है। राक्षस एक पंक्ति में खड़े हैं, iवें राक्षस का निर्देशांक X[i] है, और उसका स्वास्थ्य H[i] है। चांदी की लोमड़ी राक्षसों पर हमला करने के लिए बमों का उपयोग कर सकती है। स्थान x पर बम गिराने से x - D से x + D की रेंज में सभी राक्षसों को नुकसान होगा। उनका स्वास्थ्य A से कम हो जाएगा। जब सभी राक्षसों का स्वास्थ्य 0 रह जाता है, तो लोमड़ी जीत जाती है। हमें जीतने के लिए आवश्यक न्यूनतम संभव स्थान ढूंढने हैं।

उदाहरण के लिए, यदि इनपुट D = 3; A = 2; X = [1, 5, 9]; H = [2, 4, 2] है, तो आउटपुट 2 होगा, क्योंकि पहला बम निर्देशांक 4 पर, नए स्वास्थ्य मान [0, 2, 2], फिर स्थिति 6 पर सभी स्वास्थ्य मान [0, 0, 0] बनाने के लिए।

चरण

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:

एक बड़ा ऐरे q परिभाषित करें x और h युग्मों का एक ऐरे परिभाषित करें n := X का आकार d := D a := A i := 1 से n तक, करें: num[i].x := X[i - 1] num[i].h := H[i - 1] ऐरे num को सॉर्ट करें sum := 0 i := 1 से n तक, करें: q[i] := q[i] + q[i - 1] num[i].h := num[i].h - q[i] * a यदि num[i].h <= 0, तो: अगले पुनरावृत्ति पर जाएं p := (यदि num[i].h mod a, 0 के बराबर है, तो num[i].h / a, अन्यथा num[i].h / a + 1) tmp := num[i].x + 2 * d sum := sum + p q[i] := q[i] + p l := i, r = n जब तक l < r, करें: mid := (l + r + 1) / 2 यदि num[mid].x <= tmp, तो: l := mid अन्यथा r := mid - 1 q[l + 1] -= p sum वापस करें

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

#include <bits/stdc++.h> using namespace std; const int maxn = 2e5 + 20; int n; int d, a, q[maxn]; struct node{    int x, h;    bool operator<(const node& a) const{       return x < a.x;    } } num[maxn]; int solve(int D, int A, vector<int> X, vector<int> H){    n = X.size();    d = D;    a = A;    for (int i = 1; i <= n; i++){       num[i].x = X[i - 1];       num[i].h = H[i - 1];    }    sort(num + 1, num + n + 1);    int sum = 0;    for (int i = 1; i <= n; i++){       q[i] += q[i - 1];       num[i].h -= q[i] * a;       if (num[i].h <= 0)          continue;       int p = (num[i].h % a == 0 ? num[i].h / a : num[i].h / a + 1);       int tmp = num[i].x + 2 * d;       sum += p;       q[i] += p;       int l = i, r = n;       while (l < r){          int mid = (l + r + 1) >> 1;          if (num[mid].x <= tmp)             l = mid;          else             r = mid - 1;       }       q[l + 1] -= p;    }    return sum; } int main(){    int D = 3;    int A = 2;    vector<int> X = { 1, 5, 9 };    vector<int> H = { 2, 4, 2 };    cout << solve(D, A, X, H) << endl; }

इनपुट

3, 2, { 1, 5, 9 }, { 2, 4, 2 }

आउटपुट

2

  1. C++ में प्रतिद्वंद्वी को पकड़ने के लिए आवश्यक न्यूनतम चरणों की संख्या ढूंढने का प्रोग्राम C++ में प्रतिद्वंद्वी को पकड़ने के लिए आवश्यक न्यूनतम चरणों की संख्या ढूंढने का प्रोग्राम

    परिचय मान लीजिए हमारे पास ट्री एजेज की एक सूची है [u, v] के रूप में, जो इंगित करती है कि u और v के बीच एक अनडायरेक्टेड एज है। और हमारे पास दो मान x और y भी हैं। यदि हम नोड x पर हैं, और हमारा प्रतिद्वंद्वी नोड y पर है। पहले राउंड में हम चलते हैं, फिर अगले राउंड में प्रतिद्वंद्वी चलता है और इसी तरह।

  1. - C++ में शतरंज बोर्ड में वर्गों की संख्या ढूंढना

    इस समस्या में, हमें एक शतरंज बोर्ड का आकार दिया गया है। हमारा कार्य C++ में शतरंज बोर्ड में वर्गों की संख्या ढूंढने के लिए एक प्रोग्राम बनाना है। समस्या विवरण शतरंज बोर्ड में वर्गों की संख्या ढूंढने के लिए। हमें शतरंज बोर्ड के अंदर वर्ग के सभी संयोजनों की गणना करनी होगी यानी हम 1x1, 2x2, 3x3 ... nx

  1. - C++ में 75% उपस्थिति बनाए रखने के लिए न्यूनतम व्याख्यान ढूंढना

    इस समस्या में, हमें दो संख्याएं M और N दी गई हैं जो वर्तमान तिथि तक आयोजित कुल कक्षाओं की संख्या और छात्र द्वारा उपस्थित कक्षाओं की संख्या को दर्शाती हैं। हमारा कार्य C++ में 75% उपस्थिति बनाए रखने के लिए उपस्थित होने वाले न्यूनतम व्याख्यानों की संख्या ढूंढने के लिए एक प्रोग्राम बनाना है। समस्या व