मान लीजिए हमारे पास दो ऐरे 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