Bag of Tokens trong C++

Cho sức mạnh ban đầu P, điểm 0, túi token giá trị token[i]. Mỗi token dùng tối đa 1 lần, 2 cách:

• Face up: nếu power ≥ token[i], mất token[i] power, được 1 điểm

• Face down: nếu điểm ≥ 1, được token[i] power, mất 1 điểm

Tìm điểm tối đa có thể đạt được.

Ví dụ: tokens=[100,200,300,400], P=200 → 2.

Giải pháp tham lam hai con trỏ:

• Sắp xếp tokens

• i=0, j=n-1, curr=0, ret=0

• While i≤j và power≥tokens[i]:
  While i≤j và power≥tokens[i]: power-=tokens[i], curr++, i++
  ret = max(ret, curr)
  While j≥i và curr>0 và power

• Trả về ret

Ví dụ

#include <bits/stdc++.h> using namespace std; class Solution {    public:    int bagOfTokensScore(vector<int>& v, int x) {       int n = v.size(), ret = 0;       sort(v.begin(), v.end());       int i = 0, j = n - 1, 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;    } }; int 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