C ++中的令牌袋
假设我们有一个初始功效P，一个初始得分0分和一袋代币。现在每个令牌最多可以使用一次，有一个值token[i]，并且可能有两种使用方式，这些方式如下：
如果我们至少具有token[i]功效，那么我们可以将令牌面朝上玩，失去token[i]功效，并获得1分。
否则，当我们至少有1分时，我们可能会朝下玩令牌，获得令牌[i]的力量，并失去1分。
玩任意数量的代币后，我们必须找到可以拥有的最大点数。
因此，如果输入类似于令牌=[100,200,300,400]且P=200，则输出将为2。
为了解决这个问题，我们将遵循以下步骤-
n：=数组v的大小，ret：=0
对v数组排序
设置i：=0和j：=n–1，curr：=
而我<=j和x>=v[i]
将x增加v[j]，将curr和j减少1
将x减v[i]，将curr和i减1
而我<=j和x>=v[i]
ret：=curr和ret的最大值
而j>=i且curr不为0且x<v[i]
返回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