Chương trình C++ tìm số sô-cô-la nhiều nhất mua được với tối đa k rupee

Cho mảng giá A kích thước n, và l, r, k. Chỉ mua sô-cô-la giá trong [l, r]. Tổng chi phí ≤ k. Tìm số lượng tối đa.

Ví dụ

Với A=[1,2,3,4,5,6], l=3, r=5, k=10, đầu ra 2 (mua 3 và 4 = 7 rupee).

Giải thuật

Sắp xếp A. Duyệt từ nhỏ đến lớn: nếu giá > k thì dừng; nếu giá trong [l,r] thì mua (trừ k, tăng đếm). Trả về đếm.

Mã 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, r = 5, k = 10;
    cout << solve(A, l, r, k) << endl;
}

Đầu vào / Đầu ra

Input: { 1, 2, 3, 4, 5, 6 }, 3, 5, 10
Output: 2