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