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]。

步骤

为了解决这个问题,我们将遵循以下步骤:

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

示例

让我们来看下面的实现,以便更好地理解:

Open Compiler
#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; }

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

输入

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

输出

2

更新于:2022年3月2日

234 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告