n개의 요소가 있는 배열 A가 있고 다른 값 l, r 및 k가 있다고 가정합니다. Amal은 초콜릿을 사고 싶어하며 너무 비싼 초콜릿도 사지 않고 너무 싼 초콜릿도 사지 않을 것입니다. 가게에는 n개의 서로 다른 초콜릿 바가 있고 가격은 A로 표시됩니다. 초콜릿 바는 가격이 r보다 크면 너무 비싸고 가격이 l보다 작으면 너무 싼 것입니다. 그는 기껏해야 k 루피를 쓰고 싶어합니다. 그가 살 수 있는 초콜릿의 최대량을 찾아야 합니다.
따라서 입력이 A =[1, 2, 3, 4, 5, 6]과 같으면; 내가 =3; r =5; k =10이면 출력은 2가 됩니다. 왜냐하면 그는 7루피로 3루피와 4루피 가치가 있는 초콜릿을 살 수 있기 때문입니다.
단계
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
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