मान लीजिए कि हमारे पास प्रारंभिक शक्ति पी है, 0 अंक का प्रारंभिक स्कोर और टोकन का एक बैग है। अब प्रत्येक टोकन का अधिकतम एक बार उपयोग किया जा सकता है, एक मूल्य टोकन [i] है, और इसका उपयोग करने के संभावित रूप से दो तरीके हैं, ये इस प्रकार हैं -
-
यदि हमारे पास कम से कम टोकन [i] शक्ति है, तो हम टोकन फेस अप खेल सकते हैं, टोकन [i] शक्ति खो सकते हैं, और 1 अंक प्राप्त कर सकते हैं।
-
अन्यथा जब हमारे पास कम से कम 1 अंक होता है, तो हम टोकन फेस डाउन खेल सकते हैं, टोकन [i] शक्ति प्राप्त कर सकते हैं, और 1 अंक खो सकते हैं।
हमें किसी भी संख्या में टोकन खेलने के बाद सबसे अधिक अंक प्राप्त करने होंगे।
तो अगर इनपुट टोकन =[100,200,300,400] और पी =200 की तरह है, तो आउटपुट 2 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
n :=सरणी का आकार v, ret :=0
-
v सरणी को सॉर्ट करें
-
सेट मैं :=0 और j :=n – 1, curr :=
-
जबकि मैं <=j और x>=v[i]
-
जबकि मैं <=j और x>=v[i]
-
x को v[i] से घटाएं, curr और i को 1 से बढ़ाएं
-
-
ret :=अधिकतम curr और ret
-
जबकि j>=i और curr 0 नहीं है और x
-
x को v[j] से बढ़ाएँ, 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
आउटपुट
2