সমস্ত দানবকে হত্যা করার জন্য বোমা রাখার জন্য ন্যূনতম সংখ্যক অবস্থান খুঁজে পেতে C++ প্রোগ্রাম

ধরুন আমাদের দুটি অ্যারে X এবং H আছে। উভয়ই N উপাদান সহ, এছাড়াও আরও দুটি সংখ্যা D এবং A আছে। একটি গল্পে বিবেচনা করুন, একটি রূপালী শিয়াল N দানবের সাথে লড়াই করছে। দানবগুলো সারিবদ্ধভাবে দাঁড়িয়ে আছে, ith দানবের স্থানাঙ্ক হল 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]।

পদক্ষেপ

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

Define a large array q
Define an array of x and h pairs
n := size of X
d := D
a := A
for initialize i := 1, when i <= n, update (increase i by 1), do:
   num[i].x := X[i - 1]
   num[i].h := H[i - 1]
sort the array num
sum := 0
for initialize i := 1, when i <= n, update (increase i by 1), do:
   q[i] := q[i] + q[i - 1]
   num[i].h := num[i].h - q[i] * a
   if num[i].h <= 0, then:
      Ignore following part, skip to the next iteration
   p := (if num[i].h mod a is same as 0, then num[i].h / a, otherwise num[i].h / a + 1)
   tmp := num[i].x + 2 * d
   sum := sum + p
   q[i] := q[i] + p
   l := i, r = n
   while l < r, do:
      mid := (l + r + 1) / 2
      if num[mid].x <= tmp, then:
         l := mid
      Otherwise
         r := mid - 1
      q[l + 1] - = p
return 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 }