BGN31: 清楚姐姐买竹鼠

题目分析

清楚姐姐要买至少 n 只竹鼠，有两种购买方式：单买一只花 a 元，或者买一捆（3只）花 b 元。问最少花多少钱？

拿到这道题，你会怎么想？

思路引导

首先问自己一个问题：我们是不是只要比较"单买3只"和"买一捆"哪个更划算就行了？

没那么简单。虽然如果 b < 3a，买捆更划算，但问题在于 n 不一定是 3 的倍数。比如要买 10 只，买 3 捆是 9 只，还差 1 只得单买。而买 4 捆就是 12 只，多买了 2 只但也许反而更便宜。

所以关键在于：最后那个"零头"怎么处理？

我们可以枚举买多少捆（k 捆），剩下的不够一捆的部分用单买补齐。k 的范围是 0 到 ceil(n/3)，也就是最多把全部需求都用捆买完（可能多买几只，但没关系，题目要求"至少 n 只"）。

对于每一个 k：

  • 捆买了 3k 只，花费 k*b 元
  • 还差 max(0, n - 3k) 只，单买补上，花费 max(0, n-3k)*a 元
  • 总花费取最小值

这样枚举一遍，答案就出来了。

复杂度分析

  • 时间复杂度：，即 ，枚举捆数
  • 空间复杂度：

代码实现

#include <bits/stdc++.h>
using namespace std;
int main() {
    long long a, b, n;
    cin >> a >> b >> n;
    long long ans = LLONG_MAX;
    for (long long k = 0; k <= (n / 3) + 1; k++) {
        long long remaining = max(0LL, n - 3 * k);
        long long cost = k * b + remaining * a;
        ans = min(ans, cost);
    }
    cout << ans << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();
        long n = sc.nextLong();
        long ans = Long.MAX_VALUE;
        for (long k = 0; k <= (n / 3) + 1; k++) {
            long remaining = Math.max(0, n - 3 * k);
            long cost = k * b + remaining * a;
            ans = Math.min(ans, cost);
        }
        System.out.println(ans);
    }
}

a, b, n = map(int, input().split())
ans = n * a  # all single
k = n // 3
# try k bundles + remainder single
remaining = n - 3 * k
cost = k * b + remaining * a
ans = min(ans, cost)
# try k+1 bundles (buy extra to cover)
cost = (k + 1) * b
ans = min(ans, cost)
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 [a, b, n] = lines[0].split(' ').map(BigInt);
    const k = n / 3n;
    let ans = n * a; // all single
    // k bundles + remainder single
    const r = n - 3n * k;
    let cost = k * b + r * a;
    if (cost < ans) ans = cost;
    // k+1 bundles
    cost = (k + 1n) * b;
    if (cost < ans) ans = cost;
    console.log(ans.toString());
});

总结

这道题本质上是个简单的枚举贪心。很多同学可能上来就想用数学公式一步算出答案，但其实直接枚举"买几捆"是最稳妥的做法，不容易出错。核心要注意的点就是：买多了也可以，因为题目说的是"至少 n 只"，所以多买的捆也是合法的。把这个想清楚，剩下的就是一个 for 循环的事。