题目：令牌放置
你的初始能量为P，初始分数为0，只有一包令牌tokens。其中tokens[i]是第
i个令牌的值（下标从 0 开始）。
令牌可能的两种使用方法如下：
•如果你至少有token[i]点能量，可以将令牌i置为正面朝上，失去token[i]点能量，并得到1分。
•如果我们至少有1分，可以将令牌i置为反面朝上，获得token[i]点能量，并失去1分。
每个令牌最多只能使用一次，使用顺序不限，不需使用所有令牌。
在使用任意数量的令牌后，返回我们可以得到的最大分数。
示例 1：
输入：tokens = [100], P = 50
输出：0
解释：无法使用唯一的令牌，因为能量和分数都太少了。
示例 2：
输入：tokens = [100,200], P = 150
输出：1
解释：令牌 0 正面朝上，能量变为 50，分数变为 1 。不必使用令牌 1 ，因为你无法
使用它来提高分数。
示例 3：
输入：tokens = [100,200,300,400], P = 200
输出：2
解释：按下面顺序使用令牌可以得到 2 分：
1. 令牌 0 正面朝上，能量变为 100 ，分数变为 1
2. 令牌 3 正面朝下，能量变为 500 ，分数变为 0
3. 令牌 1 正面朝上，能量变为 300 ，分数变为 1
4. 令牌 2 正面朝上，能量变为 0 ，分数变为 2
提示：
•0 <= tokens.length <= 1000
•0 <= tokens[i], P < 104
语言:java
class Solution {
public int bagOfTokensScore(int[] tokens, int P) {
Arrays.sort(tokens);
int lo = 0, hi = tokens.length - 1;
int points = 0, ans = 0;
while (lo <= hi && (P >= tokens[lo] || points > 0)) {
while (lo <= hi && P >= tokens[lo]) {
P -= tokens[lo++];
points++;
}
ans = Math.max(ans, points);
if (lo <= hi && points > 0) {
P += tokens[hi--];
points--;
}
}
return ans;
}
}
语言:java
class Solution {
public int bagOfTokensScore(int[] tokens, int P) {
//从小到大排序
Arrays.sort(tokens);
int l=0,r=tokens.length-1;
int points = 0,p = P;
while(l<=r){
if(p>=tokens[l]){
//如果当前的能量可以换积分，那就赶紧换积分；然后开始下一轮兑换                p -= tokens[l];
points ++;
l++;
}else if(points > 0 && l<r){
//如果有得分，且有最大的能量可以兑换，那就兑换能量
p+=tokens[r];
points --;
r--;
}else{
/
/无法换积分也无法换能量就退出
break;
}
}
return points;
}
}
语言:python
class Solution(object):
def bagOfTokensScore(self, tokens, P):
tokens.sort()
deque = collections.deque(tokens)
ans = bns =0
while deque and (P >= deque[0] or bns):
while deque and P >= deque[0]:
P -= deque.popleft()
bns +=1
ans = max(ans, bns)
if deque and bns:
P += deque.pop()
bns -=1
return ans
语言:cpp
class Solution {
public:
int bagOfTokensScore(vector<int>& tokens, int power) {
sort(begin(tokens), end(tokens));
pty() || power < tokens[0]) return0;
int n = tokens.size();
int ans = 1;
vector <int> s(n);
s[0] = tokens[0];
for(int i = 1; i < n; i++) s[i] = s[i - 1] + tokens[i];
for(int i = 0, j = n - 1; i <= j; i++, j--){
int p = (i > 0)? s[i - 1]: 0;
auto it = lower_bound(s.begin() + i, s.begin() + j + 1, power + p);
if(it != s.end()) {
if(*it == power + p) ans = max(ans, (int)(it - s.begin() - i) + 1);                ans = max(ans, (int)(it - s.begin() - i));
}
power += tokens[j] - tokens[i];
}
return ans;
}
};
语言:cpp
class Solution {
public:
int bagOfTokensScore(vector<int>& tokens, int power) {
sort(tokens.begin(), d());
int l = 0;
int r = tokens.size() - 1;
int res = 0;
while (l <= r)
{
if (power >= tokens[l])
{
++res;
power -= tokens[l];
++l;
}
else
{
// r-1>l 就是为了保证最后一次不会减
if (res > 0 && r-1 > l)
{
--res;
power += tokens[r];
--r;
}
else
{
// 不满足可以提前结束了
break;
}
}
}
return res;
}
};
语言:cpp
class Solution {
public:
//用最少的分数获得最多的能量然后用最少的能量获得最高的分数int bagOfTokensScore(vector<int>& tokens, int p) {
int size=tokens.size();
int score=0,res=0;
sort(tokens.begin(),d(),less<int>());
//for(int num:tokens)cout<<num<<endl;
int left=0,right=size-1;
while(left<=right){autoit
//优先兑换分数
while(left<=right&&tokens[left]<=p){
p-=tokens[left];left++;
score++;
res=max(res,score);
}
//兑换分数
if(left<=right&&score){
score--;
p+=tokens[right--];
}
else if(!score)return res;
//cout<<p<<endl;
}
return res;
}
};
语言:go
func bagOfTokensScore(tokens []int, P int) int {
sort.Ints(tokens)
left:=0
right:=len(tokens)-1
res:=0
for left<=right {
for left<=right&&tokens[left]<= P {
res++
P-=tokens[left]
left++
}
if left<right&&tokens[right]+P>=tokens[left]&&res>0 {            res--
P+=tokens[right]
right--
}else {
break
}
}
return res
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。