买橘子

思路

这道题说的是，小明要买恰好 $n$ 个橙子，商贩只卖整袋的，每袋要么 6 个要么 8 个，问最少买几袋能凑出恰好 $n$ 个，凑不出就输出 $-1$ 。

最直接的做法就是枚举。我们枚举用了多少袋 6 个装的，设为 $i$ 袋，那么剩下的 $n - 6i$ 个就必须全用 8 个装的袋子来凑。只要 $n - 6i$ 能被 8 整除，就说明这种分配方案可行，此时袋数就是 $i + (n - 6i) / 8$ 。我们在所有可行方案里取最小值就好了。

为什么这样做是对的？因为 6 个装的袋数最多用 $\lfloor n/6 \rfloor$ 袋，所以枚举范围是有限的。而且我们要最少袋数，8 个装的袋子装得更多，所以尽量多用 8 个装的会更优。枚举的过程天然会覆盖到最优解。

举个例子： $n = 20$ ，枚举 $i = 0$ 时剩 20， $20 \bmod 8 \neq 0$ ； $i = 2$ 时剩 $20 - 12 = 8$ ， $8 \bmod 8 = 0$ ，袋数 $= 2 + 1 = 3$ 。所以答案是 3。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    int ans = INT_MAX;
    for(int i = 0; i <= n/6; i++){
        int rem = n - i*6;
        if(rem % 8 == 0){
            ans = min(ans, i + rem/8);
        }
    }
    cout << (ans == INT_MAX ? -1 : 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 = Integer.MAX_VALUE;
        for (int i = 0; i <= n / 6; i++) {
            int rem = n - i * 6;
            if (rem % 8 == 0) {
                ans = Math.min(ans, i + rem / 8);
            }
        }
        System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);
    }
}

n = int(input())
ans = float('inf')
for i in range(n // 6 + 1):
    rem = n - i * 6
    if rem % 8 == 0:
        ans = min(ans, i + rem // 8)
print(-1 if ans == float('inf') else ans)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
rl.on('line', (line) => {
    const n = parseInt(line.trim());
    let ans = Infinity;
    for (let i = 0; i <= Math.floor(n / 6); i++) {
        const rem = n - i * 6;
        if (rem % 8 === 0) {
            ans = Math.min(ans, i + rem / 8);
        }
    }
    console.log(ans === Infinity ? -1 : ans);
    rl.close();
});

复杂度分析

时间复杂度： $O(n/6)$ ，即 $O(n)$ 。枚举 6 个装的袋数，最多循环 $\lfloor n/6 \rfloor + 1$ 次。
空间复杂度： $O(1)$ ，只用了几个变量。