Skip to content

Latest commit

 

History

History
203 lines (156 loc) · 7.02 KB

README_EN.md

File metadata and controls

203 lines (156 loc) · 7.02 KB
comments difficulty edit_url rating source tags
true
Medium
1591
Biweekly Contest 134 Q2
Greedy
Array

3207. Maximum Points After Enemy Battles

中文文档

Description

You are given an integer array enemyEnergies denoting the energy values of various enemies.

You are also given an integer currentEnergy denoting the amount of energy you have initially.

You start with 0 points, and all the enemies are unmarked initially.

You can perform either of the following operations zero or multiple times to gain points:

  • Choose an unmarked enemy, i, such that currentEnergy >= enemyEnergies[i]. By choosing this option: 
    <ul>
	<li>You gain 1 point.</li>
	<li>Your energy is reduced by the enemy&#39;s energy, i.e. <code>currentEnergy = currentEnergy - enemyEnergies[i]</code>.</li>
</ul>
</li>
<li>If you have <strong>at least</strong> 1 point, you can choose an <strong>unmarked</strong> enemy, <code>i</code>. By choosing this option:
<ul>
	<li>Your energy increases by the enemy&#39;s energy, i.e. <code>currentEnergy = currentEnergy + enemyEnergies[i]</code>.</li>
	<li>The <font face="monospace">e</font>nemy <code>i</code> is <strong>marked</strong>.</li>
</ul>
</li>

Return an integer denoting the maximum points you can get in the end by optimally performing operations.

 

Example 1:

Input: enemyEnergies = [3,2,2], currentEnergy = 2

Output: 3

Explanation:

The following operations can be performed to get 3 points, which is the maximum:

  • First operation on enemy 1: points increases by 1, and currentEnergy decreases by 2. So, points = 1, and currentEnergy = 0.
  • Second operation on enemy 0: currentEnergy increases by 3, and enemy 0 is marked. So, points = 1, currentEnergy = 3, and marked enemies = [0].
  • First operation on enemy 2: points increases by 1, and currentEnergy decreases by 2. So, points = 2, currentEnergy = 1, and marked enemies = [0].
  • Second operation on enemy 2: currentEnergy increases by 2, and enemy 2 is marked. So, points = 2, currentEnergy = 3, and marked enemies = [0, 2].
  • First operation on enemy 1: points increases by 1, and currentEnergy decreases by 2. So, points = 3, currentEnergy = 1, and marked enemies = [0, 2].

Example 2:

Input: enemyEnergies = [2], currentEnergy = 10

Output: 5

Explanation:

Performing the first operation 5 times on enemy 0 results in the maximum number of points.

 

Constraints:

  • 1 <= enemyEnergies.length <= 105
  • 1 <= enemyEnergies[i] <= 109
  • 0 <= currentEnergy <= 109

Solutions

Solution 1: Greedy + Sorting

According to the problem description, we need to score by defeating enemies with the lowest energy value and increase our energy value by defeating enemies with the highest energy value and marking them.

Therefore, we can sort the enemies by their energy values, then start from the enemy with the highest energy value, always choose the enemy with the lowest energy value to score and consume energy. Next, we add the energy value of the enemy with the highest energy to our current energy and mark that enemy. Repeat the above steps until all enemies are marked.

The time complexity is $O(n \log n)$, and the space complexity is $O(\log n)$, where $n$ is the number of enemies.

Python3

class Solution:
    def maximumPoints(self, enemyEnergies: List[int], currentEnergy: int) -> int:
        enemyEnergies.sort()
        if currentEnergy < enemyEnergies[0]:
            return 0
        ans = 0
        for i in range(len(enemyEnergies) - 1, -1, -1):
            ans += currentEnergy // enemyEnergies[0]
            currentEnergy %= enemyEnergies[0]
            currentEnergy += enemyEnergies[i]
        return ans

Java

class Solution {
    public long maximumPoints(int[] enemyEnergies, int currentEnergy) {
        Arrays.sort(enemyEnergies);
        if (currentEnergy < enemyEnergies[0]) {
            return 0;
        }
        long ans = 0;
        for (int i = enemyEnergies.length - 1; i >= 0; --i) {
            ans += currentEnergy / enemyEnergies[0];
            currentEnergy %= enemyEnergies[0];
            currentEnergy += enemyEnergies[i];
        }
        return ans;
    }
};

C++

class Solution {
public:
    long long maximumPoints(vector<int>& enemyEnergies, int currentEnergy) {
        sort(enemyEnergies.begin(), enemyEnergies.end());
        if (currentEnergy < enemyEnergies[0]) {
            return 0;
        }
        long long ans = 0;
        for (int i = enemyEnergies.size() - 1; i >= 0; --i) {
            ans += currentEnergy / enemyEnergies[0];
            currentEnergy %= enemyEnergies[0];
            currentEnergy += enemyEnergies[i];
        }
        return ans;
    }
};

Go

func maximumPoints(enemyEnergies []int, currentEnergy int) (ans int64) {
	sort.Ints(enemyEnergies)
	if currentEnergy < enemyEnergies[0] {
		return 0
	}
	for i := len(enemyEnergies) - 1; i >= 0; i-- {
		ans += int64(currentEnergy / enemyEnergies[0])
		currentEnergy %= enemyEnergies[0]
		currentEnergy += enemyEnergies[i]
	}
	return
}

TypeScript

function maximumPoints(enemyEnergies: number[], currentEnergy: number): number {
    enemyEnergies.sort((a, b) => a - b);
    if (currentEnergy < enemyEnergies[0]) {
        return 0;
    }
    let ans = 0;
    for (let i = enemyEnergies.length - 1; ~i; --i) {
        ans += Math.floor(currentEnergy / enemyEnergies[0]);
        currentEnergy %= enemyEnergies[0];
        currentEnergy += enemyEnergies[i];
    }
    return ans;
}