Minimum Amount of Damage Dealt to Bob

Problem Description

Ah, the classic dilemma of dealing with enemies while trying to minimize damage—sounds like a typical Tuesday, right? Imagine you’re Bob, a hero with a power level that could rival a toddler with a toy sword. You’re up against a horde of enemies, each with their own unique damage output and health points. Your goal? To take them down while sustaining the least amount of damage possible.

In this LeetCode problem, you’re tasked with calculating the minimum damage Bob will take while defeating all enemies. It’s like trying to eat a whole pizza by yourself without gaining a single calorie—impossible, but we can dream!

Code Solution


struct Enemy {
  int damage;
  int timeTakenDown;
};

class Solution {
 public:
  long long minDamage(int power, vector& damage, vector& health) {
    long ans = 0;
    long sumDamage = accumulate(damage.begin(), damage.end(), 0L);
    vector enemies;

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

    ranges::sort(enemies, ranges::greater{}, [](const Enemy& e) {
      return static_cast(e.damage) / e.timeTakenDown;
    });

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

    return ans;
  }
};

Approach

The approach taken in this solution is quite strategic. First, we calculate the total damage from all enemies. Then, we create a list of enemies, each represented by their damage and the time it takes to take them down. The key insight here is that it’s more beneficial to take down enemies with a higher damage-to-time ratio first. This is achieved by sorting the enemies based on this ratio and then calculating the total damage Bob would take as he defeats them in that order.

Time and Space Complexity

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

Real-World Example

Imagine you’re at a buffet, and you want to eat as much as possible without feeling sick. You have to choose which dishes to tackle first based on how filling they are. If you start with the heavy lasagna, you might not have room for the light salad later. Similarly, in this problem, Bob must prioritize which enemies to defeat first based on their damage output and the time it takes to defeat them.