Bag of Tokens ใน C++

คำอธิบายปัญหา

มีพลังเริ่มต้น P, คะแนน 0, และถุงโทเคน แต่ละโทเคนมีค่า token[i] สามารถใช้ได้ 2 แบบ:

• Face up: จ่ายพลัง token[i] ได้ 1 คะแนน (ต้องมีพลังพอ)
• Face down: ได้พลัง token[i] เสีย 1 คะแนน (ต้องมีคะแนนอย่างน้อย 1)

โทเคนแต่ละอันใช้ได้สูงสุด 1 ครั้ง ต้องการคะแนนสูงสุด

ตัวอย่าง: tokens=[100,200,300,400], P=200 → 2

วิธีแก้ปัญหา (Two Pointers + Greedy)

1. เรียงโทเคนจากน้อยไปมาก
2. ใช้ two pointers: i (ซ้าย = โทเคนเล็ก), j (ขวา = โทเคนใหญ่)
3. พยายามใช้โทเคนเล็ก face up (ได้คะแนน) จนพลังไม่พอ
4. แลกโทเคนใหญ่ face down (ได้พลัง) เพื่อเล่นต่อ
5. ติดตามคะแนนสูงสุดตลอด

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int bagOfTokensScore(vector<int>& tokens, int P) {
        sort(tokens.begin(), tokens.end());
        int n = tokens.size();
        int i = 0, j = n - 1;
        int score = 0, maxScore = 0;
        
        while(i <= j && P >= tokens[i]) {
            // ใช้โทเคนเล็ก face up
            while(i <= j && P >= tokens[i]) {
                P -= tokens[i];
                score++;
                i++;
            }
            maxScore = max(maxScore, score);
            
            // แลกโทเคนใหญ่ face down
            while(i <= j && score > 0 && P < tokens[i]) {
                score--;
                P += tokens[j];
                j--;
            }
        }
        return maxScore;
    }
};

int main() {
    vector<int> v1 = {100,200,300,400};
    Solution ob;
    cout << ob.bagOfTokensScore(v1, 200);
    return 0;
}

อินพุต

[100,200,300,400] 200

เอาต์พุต

2