数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++中的令牌包
假设我们拥有初始能量 P，初始分数为 0 分，以及一个令牌包。现在每个令牌最多只能使用一次，每个令牌都有一个值 token[i]，并且可能有两种使用方法：
如果我们至少拥有 token[i] 的能量，我们可以正面朝上放置令牌，损失 token[i] 能量，获得 1 分。
否则，如果我们至少有 1 分，我们可以反面朝上放置令牌，获得 token[i] 能量，损失 1 分。
我们需要找到我们可以获得的最大分数。
例如，如果输入是 tokens = [100,200,300,400] 和 P = 200，则输出为 2。
为了解决这个问题，我们将遵循以下步骤：
n := 数组 v 的大小，ret := 0
对 v 数组进行排序
设置 i := 0 和 j := n – 1，curr := P
当 i <= j 且 x >= v[i] 时
当 i <= j 且 x >= v[i] 时
x 减去 v[i]，curr 和 i 加 1
ret := curr 和 ret 的最大值
当 j >= i 且 curr 不为 0 且 x < v[i] 时
x 加上 v[j]，curr 和 j 减 1
返回 ret
让我们看下面的实现来更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int bagOfTokensScore(vector<int>& v, int x) {
int n = v.size();
int ret = 0;
sort(v.begin(), v.end());
int i = 0;
int j = n - 1;
int curr = 0;
while(i <= j && x >= v[i]){
while(i <= j && x >= v[i]){
x -= v[i];
curr++;
i++;
}
ret = max(curr, ret);
while(j >= i && curr && x < v[i]){
curr--;
x += v[j];
j--;
}
}
return ret;
}
};
main(){
vector<int> v1 = {100,200,300,400};
Solution ob;
cout << (ob.bagOfTokensScore(v1, 200));
}输入
[100,200,300,400] 200
输出
2
更新于：2020年4月30日
328 次浏览
广告