C++ में टोकन बैग (Bag of Tokens)

मान लीजिए हमारे पास प्रारंभिक शक्ति P, 0 अंकों का प्रारंभिक स्कोर, और टोकन्स का एक बैग है। प्रत्येक टोकन का अधिकतम एक बार उपयोग किया जा सकता है, इसका मान token[i] है, और इसके दो संभावित उपयोग हैं:

यदि हमारे पास कम से कम token[i] शक्ति है, तो हम टोकन को फेस अप खेल सकते हैं, token[i] शक्ति खोकर 1 अंक प्राप्त करते हैं।
अन्यथा, यदि हमारे पास कम से कम 1 अंक है, तो हम टोकन को फेस डाउन खेल सकते हैं, token[i] शक्ति प्राप्त करके 1 अंक खोते हैं।

हमें किसी भी संख्या में टोकन्स खेलने के बाद प्राप्त होने वाले अधिकतम अंकों की संख्या खोजनी है।

उदाहरण के लिए, यदि tokens = [100,200,300,400] और P = 200 है, तो आउटपुट 2 होगा।

समाधान दृष्टिकोण

टोकन्स ऐरे को सॉर्ट करें
दो पॉइंटर्स i=0, j=n-1, curr=0, ret=0
जब तक i ≤ j और x ≥ v[i]:
छोटे टोकन्स से अंक प्राप्त करें (फेस अप)
ret अपडेट करें
बड़े टोकन्स से शक्ति प्राप्त करें (फेस डाउन) यदि आवश्यक हो
ret लौटाएं

C++ कार्यान्वयन

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

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

इनपुट

[100,200,300,400] 200