C++의 토큰 백

<시간/>

초기 전력 P, 초기 점수 0점, 토큰 한 봉지가 있다고 가정합니다. 이제 각 토큰은 최대 한 번만 사용할 수 있으며 값 토큰[i]이 있으며 잠재적으로 두 가지 사용 방법이 있습니다.

토큰[i] 파워 이상이면 토큰을 앞면이 보이도록 플레이하여 토큰[i] 파워를 잃고 1점을 얻을 수 있습니다.
그렇지 않으면 우리가 최소 1포인트를 가지고 있을 때 토큰을 뒤집어서 플레이하여 토큰[i] 파워를 얻고 1포인트를 잃을 수 있습니다.

많은 토큰을 플레이한 후 얻을 수 있는 가장 많은 점수를 찾아야 합니다.

따라서 입력이 토큰 =[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]
  - v[i]만큼 x 감소, curr 및 i 증가 1
- ret :=curr 및 ret의 최대값
- j>=i이고 curr은 0이 아니며 x
  - v[j]만큼 x 증가, curr 및 j 감소 1
리턴 렛

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

#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