We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Amount of Damage Dealt to Bob

Difficulty: Hard

Problem Description

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.

Key Insights

  • Bob must choose the optimal enemy to attack each second to minimize the total damage taken.
  • The order of defeating enemies significantly affects the total damage due to the damage they deal while alive.
  • The problem can be approached using a greedy algorithm or a priority queue to efficiently track the most damaging enemies.

Space and Time Complexity

Time Complexity: O(n log n) - Sorting the enemies based on their damage and health takes O(n log n), and processing them takes O(n). Space Complexity: O(n) - For storing the sorted enemies.

Solution

To solve the problem, we first create a list of enemies consisting of their damage and health points. We sort this list based on the damage dealt by enemies in descending order, as we want to eliminate the most damaging enemies first. Then, we simulate each second where Bob takes damage from all alive enemies and chooses one enemy to attack. We keep track of the total damage taken until all enemies are dead. This approach ensures that Bob minimizes his total damage taken by efficiently targeting the most threatening enemies first.

Code Solutions

def minimum_damage(power, damage, health):
    enemies = sorted(zip(damage, health), key=lambda x: -x[0])  # Sort enemies by damage in descending order
    total_damage = 0
    seconds = 0

    while enemies:
        seconds += 1  # Each loop iteration represents one second
        new_enemies = []
        
        for d, h in enemies:
            if h > 0:
                total_damage += d  # Bob takes damage from this enemy
                remaining_health = h - power  # Bob attacks this enemy
                if remaining_health > 0:
                    new_enemies.append((d, remaining_health))  # Enemy is still alive, add to the new list
        
        enemies = new_enemies  # Update the list of enemies for the next second

    return total_damage
← Back to All Questions