LeetCode 3273: Minimum Amount of Damage Dealt to Bob

Explanation

To solve this problem, we can simulate the process of Bob attacking enemies and enemies dealing damage to Bob. We iterate over the enemies, keeping track of the time it takes to defeat each enemy. We sort the enemies based on their time to defeat, so that we always choose the enemy with the highest time to defeat next.

1. Create a list of pairs (time to defeat, damage per second) for each enemy.
2. Sort the list of pairs in descending order of time to defeat.
3. Initialize total damage to 0.
4. Iterate over the sorted list, calculating the total damage Bob receives before defeating each enemy.
5. Update total damage and move to the next enemy.

Time Complexity: O(n log n) where n is the number of enemies. Space Complexity: O(n) for storing the list of pairs.

class Solution {
    public int minDamageDealt(int power, int[] damage, int[] health) {
        int n = damage.length;
        long totalDamage = 0;

        List<int[]> enemies = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int timeToDefeat = (int) Math.ceil((double) health[i] / power);
            enemies.add(new int[]{timeToDefeat, damage[i]});
        }

        Collections.sort(enemies, (a, b) -> b[0] - a[0]);

        for (int[] enemy : enemies) {
            totalDamage += (long) enemy[1] * enemy[0];
        }

        return (int) totalDamage;
    }
}