กระเป๋าโทเค็นในภาษา C++

สมมติว่าเรามีกำลังเริ่มต้น P คะแนนเริ่มต้นเป็น 0 คะแนน และโทเค็นหนึ่งถุง ตอนนี้แต่ละโทเค็นสามารถใช้ได้สูงสุดครั้งเดียว มี value token[i] และอาจมีสองวิธีในการใช้งาน เหล่านี้มีดังนี้ -

• หากเรามีพลัง token[i] อย่างน้อย เราก็อาจเล่นโทเค็นหงายหน้า สูญเสียพลัง token[i] และได้รับ 1 แต้ม

• มิฉะนั้นเมื่อเรามีอย่างน้อย 1 แต้ม เราอาจเล่นโทเค็นคว่ำหน้า ได้รับพลัง token[i] และเสีย 1 แต้ม

เราต้องหาแต้มให้ได้มากที่สุดหลังจากเล่นโทเค็นจำนวนเท่าใดก็ได้

ดังนั้นหากอินพุตเป็นเหมือนโทเค็น =[100,200,300,400] และ P =200 ผลลัพธ์จะเป็น 2

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของอาร์เรย์ v, ret :=0

• จัดเรียง v อาร์เรย์

• ตั้งค่า 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 โดย v[j] ลดสกุลเงิน และ 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