【leetcode刷题】T180-令牌放置
木又连续日更第22天（22/100）
木又的第180篇leetcode解题报告
贪心类型第9篇解题报告
leetcode第948题：令牌放置
https://leetcode-cn.com/problems/bag-of-tokens
【题目】
你的初始能量为 P，初始分数为 0，只有一包令牌。
令牌的值为 token[i]，每个令牌最多只能使用一次，可能的两种使用方法如下：
如果你至少有 token[i] 点能量，可以将令牌置为正面朝上，失去 token[i] 点能量，并得到 1 分。 如果我们至少有 1 分，可以将令牌置为反面朝上，获得 token[i] 点能量，并失去 1 分。 在使用任意数量的令牌后，返回我们可以得到的最大分数。
示例 1：
输入：tokens = [100], P = 50
输出：0
示例 2：
输入：tokens = [100,200], P = 150
输出：1
示例 3：
输入：tokens = [100,200,300,400], P = 200
输出：2
提示：
tokens.length <= 1000 0 <= tokens[i] < 10000 0 <= P < 10000
【思路】
题目描述得有点复杂，简单来说：我有一些手牌，有初始能量P，初始得分score，我只能进行两个操作，一是消耗相应能量消灭某个手牌，增加1个得分，二是消耗1个得分消灭某个手牌，增加相应能力，那么能够得到的最大分数是多少。
很容易想到，消耗能量消灭手牌点数小的，消耗得分消灭手牌点数大的，求得此过程中最大得分即可。
【代码】
python版本
class Solution(object):
def bagOfTokensScore(self, tokens, P):
"""
:type tokens: List[int]
:type P: int
:rtype: int
"""
tokens.sort()
count = 0
max_count = 0
while len(tokens) != 0:
if tokens[0] <= P:
P -= tokens.pop(0)
count += 1
max_count = max(max_count, count)
else:
if count <= 0:
break
P += tokens.pop(-1)
count -= 1
return max_count
C++版本
class Solution {
public:
int bagOfTokensScore(vector<int>& tokens, int P) {
sort(tokens.begin(), tokens.end());
int i = 0, j = tokens.size() - 1;
int count = 0, max_count = 0;
while(i <= j){
if(tokens[i] <= P){
P -= tokens[i];
i++;
count++;
max_count = max(max_count, count);
}else{
if(count <= 0)
break;
count--;
P += tokens[j];
j--;
}
}
return max_count;
}
};
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-10-09，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
