![](https://img.shields.io/badge/分数-1591-4051B5?style=flat-square)
题目描述
给你一个下标从 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
解法
方法一:贪心 + 排序
根据题目描述,我们每次需要通过具有最小能量值的敌人来获得分数,通过具有最大能量值的敌人来增加能量值并进行标记。
因此,我们可以对敌人的能量值进行排序,然后从能量值最大的敌人开始,每次都选择能量值最小的敌人来获得分数,并消耗能量值。然后,我们将能量值最大的敌人的能量值加到当前能量值上,并标记该敌人。重复上述操作,直到所有敌人都被标记。
时间复杂度 $O(n \times \log n)$,空间复杂度 $O(\log n)$。其中 $n$ 是敌人的数量。
| 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;
}
|