# 948. Bag of Tokens 令牌放置

@TOC

## # 题目描述

You have an initial power `P`, an initial score of `0` points, and a bag of tokens.

Each token can be used at most once, has a value `token[i]`, and has potentially two ways to use it.

• If we have at least `token[i]` power, we may play the token face up, losing `token[i]` power, and gaining `1` point.
• If we have at least `1` point, we may play the token face down, gaining `token[i]` power, and losing `1` point.

Return the largest number of points we can have after playing any number of tokens.

Example 1:

``````Input: tokens = [100], P = 50
Output: 0
``````

Example 2:

``````Input: tokens = [100,200], P = 150
Output: 1
``````

Example 3:

``````Input: tokens = [100,200,300,400], P = 200
Output: 2
``````

Note:

1. tokens.length <= 1000
2. 0 <= tokens[i] < 10000
3. 0 <= P < 10000

## # 题目大意

1. 当power超过token[i]的时候，可以把token[i]进行翻转成正面，然后得到了1个点；
2. 当至少有1个点的时候，可以把任何一个token[i]进行翻转成反面，然后丢失1个点。

## # 解题方法

### # 贪心算法

``````class Solution(object):
def bagOfTokensScore(self, tokens, P):
"""
:type tokens: List[int]
:type P: int
:rtype: int
"""
print(tokens)
tokens.sort()
N = len(tokens)
left, right = 0, N - 1
points = 0
remain = N
while left < N and P >= tokens[left]:
P -= tokens[left]
points += 1
left += 1
remain -= 1
if left == 0 or left == N: return points
while points > 0 and remain > 1:
P += tokens[right]
right -= 1
points -= 1
remain -= 1
while left <= right and P >= tokens[left]:
P -= tokens[left]
points += 1
left += 1
remain -= 1
return points
``````

## # 日期

2018 年 11 月 24 日 —— 周日开始！一周就过去了～