题解 | #买橘子#

题目链接

买橘子

题目描述

小明想购买恰好 $n$ 个橘子。水果商贩只提供每袋 $6$ 个和每袋 $8$ 个的包装。小明希望在能买到恰好 $n$ 个橘子的前提下，购买的总袋数最少。如果无法正好买到 $n$ 个，则不购买。

解题思路

这是一个典型的线性丢番图方程问题，但由于数据范围很小，我们可以使用更直观的枚举法。

设购买 $i$ 袋 $8$ 个装的橘子，和 $j$ 袋 $6$ 个装的橘子。我们需要满足以下条件：

$8 \cdot i + 6 \cdot j = n$
$i \ge 0$ , $j \ge 0$
我们希望最小化总袋数 $i+j$

为了让总袋数 $i+j$ 最小，我们应该优先使用能装更多橘子的大袋子（即 $8$ 个装的）。因为用一个 $8$ 个装的袋子比用一个 $6$ 个装的袋子能用更少的袋数装更多的橘子。

所以，我们可以采用贪心策略，从多到少地枚举购买 $8$ 个装的袋数 $i$ 。

$i$ 的最大可能值是 $\lfloor n/8 \rfloor$ 。
我们让 $i$ 从 $\lfloor n/8 \rfloor$ 开始，递减到 $0$ 。
对于每一个 $i$ 的值，我们计算剩下需要购买的橘子数量 rem = n - 8 * i。
接着，我们检查 rem 是否能被 $6$ 整除。
如果 rem 能被 $6$ 整除（即 rem % 6 == 0），说明我们找到了一个可行的方案。此时， $6$ 个装的袋数 $j$ 就是 rem / 6。因为我们是从最大的 $i$ 开始枚举的，所以第一个找到的解就是总袋数 $i+j$ 最少的解。我们直接输出 $i+j$ 即可。

如果循环结束后，我们都没有找到一个可行的方案，那就说明无法恰好凑成 $n$ 个橘子，此时输出 $-1$ 。

代码

c++
java
python

#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;

    int min_bags = -1;

    // 从多到少枚举8个装的袋数
    for (int i = n / 8; i >= 0; --i) {
        int rem = n - 8 * i;
        // 如果剩下的橘子数能被6整除
        if (rem % 6 == 0) {
            int j = rem / 6;
            min_bags = i + j;
            break; // 找到第一个解就是最优解
        }
    }

    cout << min_bags << '\n';

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int minBags = -1;

        // 从多到少枚举8个装的袋数
        for (int i = n / 8; i >= 0; i--) {
            int rem = n - 8 * i;
            // 如果剩下的橘子数能被6整除
            if (rem % 6 == 0) {
                int j = rem / 6;
                minBags = i + j;
                break; // 找到第一个解就是最优解
            }
        }
        
        System.out.println(minBags);
    }
}

# 读取橘子总数n
n = int(input())

min_bags = -1

# 从多到少枚举8个装的袋数
for i in range(n // 8, -1, -1):
    rem = n - 8 * i
    # 如果剩下的橘子数能被6整除
    if rem % 6 == 0:
        j = rem // 6
        min_bags = i + j
        break  # 找到第一个解就是最优解

print(min_bags)

算法及复杂度

算法：贪心枚举。
时间复杂度：我们枚举了购买 $8$ 个装橘子的袋数，循环次数最多为 $\lfloor n/8 \rfloor + 1$ 次。因此，时间复杂度为 $O(n)$ 。
空间复杂度：只使用了有限的几个变量，因此空间复杂度为 $O(1)$ 。