跳转至

3207. 与敌人战斗后的最大分数

题目描述

给你一个下标从 0 开始的整数数组 enemyEnergies ，它表示一个下标从 0 开始的敌人能量数组。

同时给你一个整数 currentEnergy ，它表示你一开始拥有的能量值总量。

你一开始的分数为 0 ，且一开始所有的敌人都未标记。

你可以通过以下操作 之一 任意次（也可以 0 次）来得分：

  • 选择一个 未标记 且满足 currentEnergy >= enemyEnergies[i] 的敌人 i 。在这个操作中：
    • 你会获得 1 分。
    • 你的能量值减少 enemyEnergies[i] ，也就是说 currentEnergy = currentEnergy - enemyEnergies[i] 。
  • 如果你目前 至少 有 1 分，你可以选择一个 未标记 的敌人 i 。在这个操作中：
    • 你的能量值增加 enemyEnergies[i] ，也就是说 currentEnergy = currentEnergy + enemyEnergies[i] 。
    • 敌人 i 被标记 。

请你返回通过以上操作，最多 可以获得多少分。

 

示例 1：

输入：enemyEnergies = [3,2,2], currentEnergy = 2

输出：3

解释：

通过以下操作可以得到最大得分 3 分：

  • 对敌人 1 使用第一种操作：points 增加 1 ，currentEnergy 减少 2 。所以 points = 1 且 currentEnergy = 0 。
  • 对敌人 0 使用第二种操作：currentEnergy 增加 3 ，敌人 0 被标记。所以 points = 1 ，currentEnergy = 3 ，被标记的敌人包括 [0] 。
  • 对敌人 2 使用第一种操作：points 增加 1 ，currentEnergy 减少 2 。所以 points = 2 且 currentEnergy = 1 ，被标记的敌人包括[0] 。
  • 对敌人 2 使用第二种操作：currentEnergy 增加 2 ，敌人 2 被标记。所以 points = 2 ，currentEnergy = 3 且被标记的敌人包括 [0, 2] 。
  • 对敌人 1 使用第一种操作：points 增加 1 ，currentEnergy 减少 2 。所以 points = 3 ，currentEnergy = 1 ，被标记的敌人包括 [0, 2] 。

示例 2：

输入：enemyEnergies = [2], currentEnergy = 10

输出：5

解释：

通过对敌人 0 进行第一种操作 5 次，得到最大得分。

 

提示：

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

解法

方法一：贪心 + 排序

思考

每次操作为「用当前能量整除某未标记敌人得分」或「消耗 \(1\) 分换取其全部能量」。\(n\le 10^5\) 且能量可达 \(10^9\)，按回合逐步模拟次数过多。

得分操作应始终对准能量最小的敌人，能量补充则应取最大者。因此先排序，若当前能量已不足最小值则答案为 \(0\)；否则从大到小依次把最大敌人的能量并入，并在并入前用最小值尽量多地得分。排序后一遍扫描即可。

根据题目描述，我们每次需要通过具有最小能量值的敌人来获得分数，通过具有最大能量值的敌人来增加能量值并进行标记。

因此，我们可以对敌人的能量值进行排序，然后从能量值最大的敌人开始，每次都选择能量值最小的敌人来获得分数，并消耗能量值。然后，我们将能量值最大的敌人的能量值加到当前能量值上，并标记该敌人。重复上述操作，直到所有敌人都被标记。

时间复杂度 \(O(n \times \log n)\)，空间复杂度 \(O(\log n)\)。其中 \(n\) 是敌人的数量。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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;
}

评论