Problem

You are given an integer power and two integer arrays damage and health, both having length n.

Bob has n enemies, where enemy i will deal Bob damage[i] points of damage per second while they are alive (i.e. health[i] > 0).

Every second, after the enemies deal damage to Bob, he chooses one of the enemies that is still alive and deals power points of damage to them.

Determine the minimum total amount of damage points that will be dealt to Bob before all n enemies are dead.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


Input: power = 4, damage = [1,2,3,4], health = [4,5,6,8]

Output: 39

Explanation:

  * Attack enemy 3 in the first two seconds, after which enemy 3 will go down, the number of damage points dealt to Bob is `10 + 10 = 20` points.
  * Attack enemy 2 in the next two seconds, after which enemy 2 will go down, the number of damage points dealt to Bob is `6 + 6 = 12` points.
  * Attack enemy 0 in the next second, after which enemy 0 will go down, the number of damage points dealt to Bob is `3` points.
  * Attack enemy 1 in the next two seconds, after which enemy 1 will go down, the number of damage points dealt to Bob is `2 + 2 = 4` points.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


Input: power = 1, damage = [1,1,1,1], health = [1,2,3,4]

Output: 20

Explanation:

  * Attack enemy 0 in the first second, after which enemy 0 will go down, the number of damage points dealt to Bob is `4` points.
  * Attack enemy 1 in the next two seconds, after which enemy 1 will go down, the number of damage points dealt to Bob is `3 + 3 = 6` points.
  * Attack enemy 2 in the next three seconds, after which enemy 2 will go down, the number of damage points dealt to Bob is `2 + 2 + 2 = 6` points.
  * Attack enemy 3 in the next four seconds, after which enemy 3 will go down, the number of damage points dealt to Bob is `1 + 1 + 1 + 1 = 4` points.

Example 3

1
2
3
4


Input: power = 8, damage = [40], health = [59]

Output: 320

Constraints

  • 1 <= power <= 10^4
  • 1 <= n == damage.length == health.length <= 10^5
  • 1 <= damage[i], health[i] <= 10^4

Solution

Method 1 – Greedy Priority Queue

Intuition

To minimize the total damage dealt to Bob, we should always attack the enemy with the highest damage per second first, as killing them earlier reduces the total damage Bob receives. At each second, Bob attacks the alive enemy with the highest damage, reducing their health by power.

Approach

  1. Use a max-heap (priority queue) to keep track of alive enemies by their damage per second.
  2. At each second:
    • All alive enemies deal their damage to Bob.
    • Bob attacks the enemy with the highest damage, reducing their health by power.
    • If the enemy’s health drops to zero or below, remove them from the heap.
  3. Repeat until all enemies are dead.
  4. Accumulate the total damage dealt to Bob.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
public:
    long long minimumDamage(int power, vector<int>& damage, vector<int>& health) {
        int n = damage.size();
        vector<pair<int, int>> enemies;
        for (int i = 0; i < n; ++i) enemies.emplace_back(damage[i], health[i]);
        auto cmp = [](const pair<int,int>& a, const pair<int,int>& b) { return a.first < b.first; };
        priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> pq(cmp);
        for (auto& e : enemies) pq.push(e);
        long long total = 0;
        while (!pq.empty()) {
            long long curDamage = 0;
            vector<pair<int,int>> temp;
            while (!pq.empty()) {
                auto e = pq.top(); pq.pop();
                curDamage += e.first;
                temp.push_back(e);
            }
            total += curDamage;
            sort(temp.begin(), temp.end(), cmp);
            temp[0].second -= power;
            vector<pair<int,int>> next;
            for (auto& e : temp) if (e.second > 0) next.push_back(e);
            pq = priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)>(cmp, next);
        }
        return total;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def minimum_damage(power: int, damage: list[int], health: list[int]) -> int:
    import heapq
    n = len(damage)
    alive = [(-damage[i], health[i], i) for i in range(n)]
    heapq.heapify(alive)
    total = 0
    while alive:
        cur_damage = sum(-d for d, h, i in alive)
        total += cur_damage
        d, h, idx = heapq.heappop(alive)
        h -= power
        if h > 0:
            heapq.heappush(alive, (d, h, idx))
    return total

Complexity

  • ⏰ Time complexity: O(n^2 log n)
    • Each second, we may process up to n enemies, and heap operations are log n.
  • 🧺 Space complexity: O(n)
    • For the heap and enemy list.