C++でコンポートを作るための最大果物数を求める方法

問題概要

3つの整数 a、b、c が与えられます。それぞれ「レモンが a 個」「リンゴが b 個」「洋梨が c 個」あることを表します。コンポートを作るには、果物の比率を 1 : 2 : 4（レモン：リンゴ：洋梨）にする必要があります。また、果物を切って使うことはできません。この条件のもとで、コンポートを作るために使える果物の合計数の最大値を求めます。1つも作れない場合は 0 を返します。

入力例

例えば、a = 4、b = 7、c = 13 の場合、出力は 21 になります。これは、レモン3個、リンゴ6個、洋梨12個を使用でき、3 + 6 + 12 = 21 となるためです。

解法のアプローチ

この問題は非常にシンプルに解くことができます。ポイントは次の通りです。

• レモンはそのまま最大 a 個まで使用可能
• リンゴは2個で1セットのため、b ÷ 2 の切り捨て値まで使用可能
• 洋梨は4個で1セットのため、c ÷ 4 の切り捨て値まで使用可能

したがって、これら3つの値の最小値が作れる「セット数」となり、1セットあたりの合計個数である 7（1 + 2 + 4）を掛けることで答えが求まります。

return 7 * min(a, min(b / 2, c / 4));

C++での実装例

以下に実際の実装例を示します。

#include <bits/stdc++.h>
using namespace std;
int solve(int a, int b, int c){
    return 7 * min(a, min(b / 2, c / 4));
}
int main(){
    int a = 4;
    int b = 7;
    int c = 13;
    cout << solve(a, b, c) << endl;
}

入力

4, 7, 13

出力

21

計算量について

このアルゴリズムは比較と算術演算のみを行うため、時間計算量は O(1)、空間計算量も O(1) です。入力の大きさに関わらず一定時間で結果を得られる点が大きな魅力です。