【C++】予算kルピー以内で購入できるチョコレートの最大数を求めるプログラム

要素数nの配列Aと、3つの値 l・r・k が与えられているとします。Amalはチョコレートを購入したいのですが、高すぎるチョコレートも安すぎるチョコレートも買いません。店にはn種類のチョコレートバーが並んでおり、それぞれの価格は配列Aで表されています。

ここで、価格が r より大きいものは「高すぎる」、l より小さいものは「安すぎる」と定義します。また、Amalが使える金額は最大でもkルピーです。このとき、彼が購入できるチョコレートの最大個数を求めるのが本問題です。

入力例と出力例

たとえば、入力が A = [1, 2, 3, 4, 5, 6]、l = 3、r = 5、k = 10 の場合、出力は 2 になります。これは、3ルピーと4ルピーのチョコレート2個を、合計7ルピーで購入できるためです。

解法のアプローチ

この問題は貪欲法（グリーディ法）を使うことで効率的に解けます。できるだけ多くのチョコレートを買いたいなら、価格の安いものから順に購入していくのが最適だからです。具体的には、以下の手順で処理を行います。

1. 配列Aを昇順にソートする。
2. 安い方から順に各価格を確認し、予算kを超えた時点でループを抜ける。
3. 価格が範囲 [l, r] 内に収まっている場合のみ、予算から差し引いてカウントを1増やす。

アルゴリズムの擬似コード

n := Aのサイズ
ans := 0
配列Aをソートする
i := 0 で初期化し、i < n の間、i を1ずつ増やしながら繰り返し:
    if A[i] > k then:
        ループを抜ける
    if A[i] >= l かつ A[i] <= r then:
        k := k - A[i]
        ans := ans + 1
return ans

C++による実装例

それでは、実際の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

計算量について

このアルゴリズムの計算量は、ソートに O(n log n)、その後の走査に O(n) かかるため、全体として O(n log n) となります。ソート済みの配列に対しては線形時間で処理できるため、非常に効率的な解法といえます。