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

คำอธิบายปัญหา

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

ตัวอย่าง: A = [1, 2, 3, 4, 5, 6]; l = 3; r = 5; k = 10 ผลลัพธ์คือ 2 เพราะซื้อราคา 3 และ 4 ใช้เงิน 7 บาท

ขั้นตอนการแก้ปัญหา

n := ขนาดของ A
ans := 0
เรียงลำดับ A
สำหรับ i := 0 ถึง n-1:
    ถ้า A[i] > k: หยุดลูป
    ถ้า A[i] >= l และ A[i] <= r:
        k := k - A[i]
        เพิ่ม ans ขึ้น 1
คืนค่า ans

ตัวอย่างโค้ด C++

#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