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