3207. Maximum Points After Enemy Battles

Intuition

The problem is about managing energy to maximize points by choosing when to spend energy on enemies to gain points and when to gain energy from enemies by marking them.

Key observations:

1. Gaining Points: You gain points by spending energy to overcome enemies.
2. Gaining Energy: You can increase your energy by marking enemies, which allows you to overcome more enemies.

Approach

1. Initialize Variables: Start with 0 points and the given initial energy.
2. Loop Through Operations: - Iterate over the enemies to spend energy and gain points as long as the current energy allows. - If the current energy is insufficient but you have at least 1 point, use a point to mark an enemy and gain its energy.
3. Break When No More Moves: Exit the loop when no more points can be gained or energy can be recovered.

Detailed steps:

1. Try to Gain Points: For each enemy, if you have enough energy, reduce your energy by the enemy's energy value and increase your points by 1.
2. Gain Energy: If you run out of energy but have points, choose an enemy to mark and add its energy to your current energy.
3. Repeat: Continue the process until you cannot perform any more operations.

Complexity

• Time Complexity: \(O(n)\), where \(n\) is the number of enemies. Each enemy is processed once.
• Space Complexity: \(O(1)\) additional space, as we use a few variables to keep track of points and current energy.

Code

C++

class Solution {
public:
    long long maximumPoints(vector& enemyEnergies, int currentEnergy) {
        int minimumEnergy = *min_element(enemyEnergies.begin(), enemyEnergies.end());
        if (currentEnergy < minimumEnergy) return 0;
        currentEnergy -= minimumEnergy;
        currentEnergy += accumulate(enemyEnergies.begin(), enemyEnergies.end(), 0);
        return currentEnergy / minimumEnergy;
    }
};

Python

class Solution:
    def maximumPoints(self, enemyEnergies: List[int], currentEnergy: int) -> int:
        minimumEnergy = min(enemyEnergies)
        if currentEnergy < minimumEnergy:
            return 0
        currentEnergy -= minimumEnergy
        currentEnergy += sum(enemyEnergies)
        return currentEnergy // minimumEnergy

Java

public class Solution {
    public long maximumPoints(int[] enemyEnergies, int currentEnergy) {
        int minimumEnergy = Arrays.stream(enemyEnergies).min().getAsInt();
        if (currentEnergy < minimumEnergy) return 0;
        currentEnergy -= minimumEnergy;
        for (int energy : enemyEnergies) currentEnergy += energy;
        return currentEnergy / minimumEnergy;
    }
}

JavaScript

/**
 * @param {number[]} enemyEnergies
 * @param {number} currentEnergy
 * @return {number}
 */
var maximumPoints = function (enemyEnergies, currentEnergy) {
    var minimumEnergy = Math.min(...enemyEnergies);
    if (currentEnergy < minimumEnergy) return 0;
    currentEnergy -= minimumEnergy;
    currentEnergy += enemyEnergies.reduce((a, b) => a + b);
    return Math.floor(currentEnergy / minimumEnergy);
};