ধরুন আমাদের একটি প্রাথমিক শক্তি P, 0 পয়েন্টের একটি প্রাথমিক স্কোর এবং এক ব্যাগ টোকেন রয়েছে। এখন প্রতিটি টোকেন সর্বাধিক একবার ব্যবহার করা যেতে পারে, একটি মান টোকেন আছে[i], এবং এটি ব্যবহার করার সম্ভাব্য দুটি উপায় রয়েছে, সেগুলি নিম্নরূপ -
-
যদি আমাদের কমপক্ষে টোকেন[i] পাওয়ার থাকে, তাহলে আমরা টোকেন ফেস আপ খেলতে পারি, টোকেন[i] পাওয়ার হারাতে পারি এবং 1 পয়েন্ট অর্জন করতে পারি।
-
অন্যথায় যখন আমাদের কমপক্ষে 1 পয়েন্ট থাকে, আমরা টোকেন ফেস ডাউন খেলতে পারি, টোকেন[i] পাওয়ার অর্জন করতে পারি এবং 1 পয়েন্ট হারাতে পারি।
যেকোন সংখ্যক টোকেন খেলার পর আমাদের সবচেয়ে বেশি সংখ্যক পয়েন্ট খুঁজে বের করতে হবে।
সুতরাং ইনপুট যদি টোকেন =[100,200,300,400] এবং P =200 এর মত হয়, তাহলে আউটপুট হবে 2।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
n :=অ্যারের আকার v, ret :=0
-
ভি অ্যারে সাজান
-
সেট i :=0 এবং j :=n – 1, curr :=
-
যখন i <=j এবং x>=v[i]
-
যখন i <=j এবং x>=v[i]
-
x কমিয়ে v[i], curr বাড়ান এবং i 1
-
-
ret :=curr এবং ret এর সর্বোচ্চ
-
যখন j>=i এবং curr 0 এবং x
নয়-
x বাড়াও
-
-
-
রিটার্ন রিটার্ন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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
