C++のトークンのバッグ

初期パワーP、初期スコア0ポイント、およびトークンの1つのバッグがあるとします。これで、各トークンは最大で1回使用でき、値token [i]があり、潜在的に2つの使用方法があります。これらは次のとおりです-

• 少なくとも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：=

  を設定します

• 一方、i<=jおよびx>=v [i]

  • 一方、i<=jおよびx>=v [i]

    • xをv[i]減らし、currとiを1増やします

  • ret：=currとretの最大値

  • 一方、j> =iであり、currは0ではなくx

    • 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