Túi token trong C ++

Giả sử chúng ta có công suất ban đầu P, số điểm ban đầu là 0 điểm và một túi mã thông báo. Giờ đây, mỗi mã thông báo có thể được sử dụng nhiều nhất một lần, có một mã thông báo giá trị [i] và có thể có hai cách để sử dụng, những cách này như sau -

• Nếu chúng ta có ít nhất mã thông báo [i] sức mạnh, thì chúng ta có thể chơi ngửa mã thông báo, mất mã thông báo [i] sức mạnh và đạt được 1 điểm.

• Nếu không, khi chúng ta có ít nhất 1 điểm, chúng ta có thể chơi úp mã thông báo, tăng sức mạnh mã thông báo [i] và mất 1 điểm.

Chúng tôi phải tìm ra số điểm lớn nhất mà chúng tôi có thể có sau khi chơi bất kỳ số lượng mã thông báo nào.

Vì vậy, nếu đầu vào giống như mã thông báo =[100.200.300.400] và P =200, thì đầu ra sẽ là 2.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của mảng v, ret:=0

• sắp xếp mảng v

• đặt i:=0 và j:=n - 1, curr:=

• trong khi tôi <=j và x> =v [i]

  • trong khi tôi <=j và x> =v [i]

    • giảm x đi v [i], tăng curr và i lên 1

  • ret:=max của curr và ret

  • trong khi j> =i và curr không phải là 0 và x

    • tăng x lên v [j], giảm curr và j đi 1

• trả lại ret

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

[100,200,300,400]
200

Đầu ra

2