Minimum Amount of Damage Dealt to Bob

Ah, the classic dilemma of dealing with enemies while trying to minimize damage—sounds like a typical Tuesday for Bob, right? Imagine Bob, our not-so-heroic hero, facing a horde of enemies who are just itching to take him down. Each enemy has a specific amount of damage they can inflict and a certain amount of time it takes to defeat them. The catch? Bob wants to minimize the total damage he takes while dispatching these foes. It’s like trying to eat a whole pizza while avoiding the crust—difficult, but not impossible!

Language Links

C++ Solution |
Python Solution 


import java.util.Arrays;

class Enemy {
  public int damage;
  public int timeTakenDown;
  public Enemy(int damage, int timeTakenDown) {
    this.damage = damage;
    this.timeTakenDown = timeTakenDown;
  }
}

class Solution {
  public long minDamage(int power, int[] damage, int[] health) {
    long ans = 0;
    long sumDamage = Arrays.stream(damage).asLongStream().sum();
    Enemy[] enemies = new Enemy[damage.length];

    for (int i = 0; i < damage.length; ++i)
      enemies[i] = new Enemy(damage[i], (health[i] + power - 1) / power);

    Arrays.sort(enemies,
                (a, b)
                    -> Double.compare((double) b.damage / b.timeTakenDown,
                                      (double) a.damage / a.timeTakenDown));

    for (final Enemy enemy : enemies) {
      ans += sumDamage * enemy.timeTakenDown;
      sumDamage -= enemy.damage;
    }

    return ans;
  }
}

Approach Explanation

The code begins by creating an Enemy class to encapsulate the damage and time taken to defeat each enemy. The minDamage method calculates the total damage Bob would take based on the enemies he faces. It first computes the total damage from all enemies and then sorts them based on their damage-to-time ratio. This way, Bob can prioritize taking down the most dangerous enemies first, minimizing the damage he incurs over time.

Time and Space Complexity

Complexity Type Complexity
Time Complexity O(n log n)
Space Complexity O(n)

Real-World Example

Imagine Bob is at a party, and he has to deal with a group of friends who are all trying to convince him to try their weird food concoctions. Each friend has a different level of persuasion (damage) and takes a different amount of time to convince him (time taken down). Bob wants to minimize the overall awkwardness (damage) he experiences while trying to enjoy the party. By strategically choosing which friends to appease first, he can minimize the cringe factor!

Similar Problems

If you enjoyed this problem, you might also like these: