买橘子

思路

题目很直白：你想买恰好 n 个橘子，商家只卖两种袋装——6 个一袋和 8 个一袋，袋子不能拆开，问最少买几袋？凑不出来就输出 -1。

本质上就是求最小的非负整数解 $a + b$ ，使得 $6a + 8b = n$ 。

怎么做最简单？贪心——优先多用大袋（8个装），因为同样的橘子数，用大袋数量更少。具体来说，从 $b = \lfloor n/8 \rfloor$ 开始往下试，每次算一下剩余的 $n - 8b$ 能不能被 6 整除，能的话答案就是 $b + (n-8b)/6$ ，直接输出。如果 $b$ 一路减到 0 都不行，那就输出 -1。

为什么从大到小枚举 8 的个数就能保证最优？因为 8 > 6，用一个 8 袋替换掉等量的 6 袋，总袋数一定不会增加。所以第一个找到的合法方案就是最优方案。

举个例子：n = 20。先试 $b = 2$ ，剩 $20 - 16 = 4$ ，4 不能被 6 整除；再试 $b = 1$ ，剩 $20 - 8 = 12$ ， $12 / 6 = 2$ ，答案就是 $1 + 2 = 3$ 。

代码

C++
Java
Python3
JavaScript

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int ans = -1;
    for (int b = n / 8; b >= 0; b--) {
        int rem = n - 8 * b;
        if (rem % 6 == 0) {
            ans = b + rem / 6;
            break;
        }
    }
    cout << ans << endl;
    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 ans = -1;
        for (int b = n / 8; b >= 0; b--) {
            int rem = n - 8 * b;
            if (rem % 6 == 0) {
                ans = b + rem / 6;
                break;
            }
        }
        System.out.println(ans);
    }
}

n = int(input())
ans = -1
for b in range(n // 8, -1, -1):
    rem = n - 8 * b
    if rem % 6 == 0:
        ans = b + rem // 6
        break
print(ans)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    let ans = -1;
    for (let b = Math.floor(n / 8); b >= 0; b--) {
        const rem = n - 8 * b;
        if (rem % 6 === 0) {
            ans = b + rem / 6;
            break;
        }
    }
    console.log(ans);
});

复杂度

时间复杂度： $O(n/8)$ ，最多循环 $\lfloor n/8 \rfloor + 1$ 次，实际上由于 6 和 8 的最小公倍数是 24，循环最多跑 3 次就能出结果（或者判定无解），可以认为是 $O(1)$ 。
空间复杂度： $O(1)$ ，只用了几个变量。

题解 | #买橘子#

买橘子

思路

代码

复杂度