题目链接

清楚姐姐买竹鼠

题目描述

清楚姐姐需要购买至少 只竹鼠。商店提供两种购买方式：

  1. 花费 元购买1只竹鼠。
  2. 花费 元购买3只竹鼠。

求买到至少 只竹鼠所需的最小花费。

解题思路

这是一个典型的优化问题，我们需要在不同的购买组合中找到总价最低的方案。问题的核心在于比较两种购买方式的“单价”。

1. 比较单位成本 我们可以比较买3只竹鼠的两种方式的成本：

  • 方式一：买3次单只的，成本为 。
  • 方式二：买1次3只装的，成本为 。

这将我们的决策分为两种主要情况：

情况一：

  • 在这种情况下，单独购买3只竹鼠比打包购买更便宜或价格相等。这意味着打包购买没有任何优势。
  • 因此，最优策略是全部单独购买。
  • 最小花费为：。

情况二：

  • 在这种情况下，打包购买（3只装）比单独购买3只更划算。我们的策略应该是尽可能多地使用打包购买。
  • 但是，我们不一定非要恰好买 只，可以稍微多买几只，如果这样总价更低的话。这里产生了两种子策略需要比较：
    1. 策略A（凑整买法）：尽可能多地打包购买，用单只的补齐剩余部分。
      • 购买 份3只装，花费 。
      • 还剩下 只需要购买。
      • 用单只的补齐，花费 。
      • 总花费为：。
    2. 策略B（向上取整买法）：完全用3只装来满足需求，即使会多买。
      • 我们需要购买 份3只装才能确保数量足够。
      • 在整数运算中， 可以表示为 。
      • 总花费为：。
  • 在这两种子策略中，哪种更优取决于 和 的具体值以及 除以3的余数。例如，如果需要补1只，而 的价格非常高，可能直接再买一份3只装（多买2只）会更便宜。
  • 因此，最终的最小花费是这两种子策略花费的较小值：。

总结

  • 如果 ，答案是 。
  • 如果 ，答案是 。

代码

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    long long a, b, n;
    cin >> a >> b >> n;
    
    long long cost;
    if (3 * a <= b) {
        cost = n * a;
    } else {
        long long cost1 = (n / 3) * b + (n % 3) * a;
        long long cost2 = ((n + 2) / 3) * b;
        cost = min(cost1, cost2);
    }
    
    cout << cost << endl;
    
    return 0;
}

import java.util.Scanner;
import java.lang.Math;

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 cost;
        if (3 * a <= b) {
            cost = n * a;
        } else {
            long cost1 = (n / 3) * b + (n % 3) * a;
            long cost2 = ((n + 2) / 3) * b;
            cost = Math.min(cost1, cost2);
        }
        
        System.out.println(cost);
    }
}

import sys

def solve():
    a, b, n = map(int, sys.stdin.readline().split())
    
    cost = 0
    if 3 * a <= b:
        cost = n * a
    else:
        # 策略A：凑整买法
        cost1 = (n // 3) * b + (n % 3) * a
        # 策略B：向上取整买法
        cost2 = ((n + 2) // 3) * b
        cost = min(cost1, cost2)
        
    print(cost)

solve()

算法及复杂度

  • 算法：分类讨论/贪心
  • 时间复杂度：整个过程只涉及几次算术运算和比较，不依赖于 的大小。因此，时间复杂度为 。
  • 空间复杂度：我们只需要常数个变量来存储输入和中间计算结果。因此，空间复杂度为 。