โปรแกรม C++ หาจำนวนช็อคโกแลตสูงสุดที่เราสามารถซื้อได้ในราคาไม่เกิน k รูปี

สมมติว่าเรามีอาร์เรย์ A ที่มีองค์ประกอบ n และค่าอื่นๆ l, r และ k อยู่ที่นั่น อามาลต้องการซื้อช็อกโกแลตและเขาจะไม่ซื้อช็อกโกแลตราคาแพงเกินไป และไม่ควรซื้อช็อกโกแลตราคาถูกเกินไปด้วย ในร้าน มีช็อกโกแลตแท่งต่างๆ อยู่ n แท่ง และราคาแสดงอยู่ใน A แท่งช็อกโกแลตจะแพงเกินไปหากราคามากกว่า r และราคาถูกเกินไปหากราคาต่ำกว่า l เขาต้องการใช้จ่ายไม่เกิน k รูปี เราต้องหาช็อกโกแลตให้ได้มากที่สุด

ดังนั้น ถ้าอินพุตเป็น A =[1, 2, 3, 4, 5, 6]; ล. =3; r =5; k =10 แล้วผลลัพธ์จะเป็น 2 เพราะเขาสามารถซื้อช็อคโกแลตมูลค่า 3 รูปีและ 4 คูณ 7 รูปี

ขั้นตอน

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

n := size of A
ans := 0
sort the array A
for initialize i := 0, when i < n, update (increase i by 1), do:
   if A[i] > k, then:
      Come out from the loop
   if A[i] >= l and A[i] <= r, then:
      k := k - A[i]
      (increase ans by 1)
return ans

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> A, int l, int r, int k) {
   int n = A.size();
   int ans = 0;
   sort(A.begin(), A.end());
   for (int i = 0; i < n; ++i) {
      if (A[i] > k)
         break;
      if (A[i] >= l && A[i] <= r) {
         k -= A[i];
         ++ans;
      }
   }
   return ans;
}
int main() {
   vector<int> A = { 1, 2, 3, 4, 5, 6 };
   int l = 3;
   int r = 5;
   int k = 10;
   cout << solve(A, l, r, k) << endl;
}

อินพุต

{ 1, 2, 3, 4, 5, 6 }, 3, 5, 10

ผลลัพธ์

2