🤖 AI总结
主题
使用Go语言计算采购最小花费的算法问题。
摘要
通过比较三种固定方案（各买各的、全买C、混合策略），使用归一化处理简化计算，实现常数时间复杂度的贪心算法求解最小采购花费。
关键信息
- 1 三种购买方案比较
- 2 归一化处理简化逻辑
- 3 常数时间复杂度的贪心算法
2026-05-06：采购的最小花费。用go语言，你有 5 个整数：cost1、cost2、costBoth、need1、need2。
现在你可以购买三种物品来凑需求：
1. 物品A：价格是 cost1，只能用于满足“需求1”，每买一个提供 1 单位需求1。
2. 物品B：价格是 cost2，只能用于满足“需求2”，每买一个提供 1 单位需求2。
3. 物品C：价格是 costBoth，同时满足两种需求：每买一个会让需求1减少 1 且需求2减少 1（等
价于同时提供 1 单位需求1和 1 单位需求2）。
你的目标是：
• 让总的需求1满足数量至少达到 need1
• 让总的需求2满足数量至少达到 need2
在满足这两条的前提下，计算总花费的最小值。
1 <= cost1, cost2, costBoth <= 1000000。
0 <= need1, need2 <= 1000000000。
输入： cost1 = 5, cost2 = 4, costBoth = 15, need1 = 2, need2 = 3。
输出： 22。
解释：
购买 need1 = 2 个类型 1 的物品和 need2 = 3 个类型 2 的物品，总花费为 2 * 5 + 3 * 4 = 10 + 12 = 22。
任何其他有效的购买方案都会花费更多，因此最小总花费为 22。
题目来自力扣3789。
一、整体思路
要同时满足需求1=need1、需求2=need2，有三种购买方案：
• 只买A、B，不买C；
• 全买C，不买A、B；
• 买一部分C，剩下不足的用A或B补。
在这三种方案里选花费最小的即可。
二、分步详细过程 1. 输入参数
• cost1：A的单价（只供需求1）
• cost2：B的单价（只供需求2）
• costBoth：C的单价（同时供1和2各1）
• need1：需求1至少要满足的数量
• need2：需求2至少要满足的数量
2. 方案一：各买各的（A+B）
• 买 need1 个 A：花费 = cost1 × need1
• 买 need2 个 B：花费 = cost2 × need2
• 总花费 res1 = cost1×need1 + cost2×need2
• 特点：一定合法，但不一定最便宜。
3. 归一化处理（让 need1 ≤ need2）
• 如果 need1 > need2：
• 交换 need1、need2
• 交换 cost1、cost2（相当于把“需求小的”统一放到前面，逻辑不变）
• 目的：简化后续“买C”的计算，只需要考虑need1 ≤ need2的情况。
• 示例（原题）：need1=2、need2=3，无需交换。
4. 方案二：全买C（全包）
• C一次解决1和2各1，最多只能买need2 个（因为 need2 更大）
• 买 need2 个 C：花费 res2 = costBoth × need2
• 特点：满足需求1=need2（≥原need1）、需求2=need2，合法；但C可能很贵。
5. 方案三：混合策略（C + 便宜的单品）
• 先买need1 个 C：解决全部需求1、同时解决 need1 个需求2
• 需求2还剩：need2 − need1 个
• 剩下的需求2用单价更低的那个单品补（此时 cost2 已经是归一化后对应大需求的单价）
• 总花费 res3 = costBoth×need1 + cost2×(need2−need1)
• 特点：合法，通常在C适中时最优。
6. 取最小值并返回
• 在 res1、res2、res3 中选最小的
• 转成 int64（防止大数溢出）返回
• 原题示例：
• res1 = 5×2 + 4×3 = 22
• res2 = 15×3 = 45
• res3 = 15×2 + 4×1 = 34
• 最小为 22，输出 22
三、时间复杂度与空间复杂度
•时间复杂度：O(1)
• 只有几次算术运算、比较、交换，与输入大小无关。
•额外空间复杂度：O(1)
• 只用到有限几个变量（res1/res2/res3、临时交换变量），不随输入增长。
四、关键点总结
1. 只需要比较三种固定方案，无需循环/枚举；
2. 归一化（need1 ≤ need2）是简化逻辑的核心；
3. 所有运算都是常数级，能处理 1e9 级的超大需求；
4. 本质是贪心：在“全单品、全套餐、套餐+补单品”里选最优。
要不要我再给你几组测试用例，帮你验证这个逻辑在不同价格和需求下是否正确？
Go完整代码如下：
package main
import (
"fmt"
)
func minimumCost(cost1, cost2, costBoth, need1, need2 int)int64 {
res1 := cost1*need1 + cost2*need2 // 各买各的
if need1 > need2 {
need1, need2 = need2, need1
cost2 = cost1
}
res2 := costBoth * need2 // 我包了
res3 := costBoth*need1 + cost2*(need2-need1) // 混合策略
returnint64(min(res1, res2, res3))
}func main() {
cost1 := 5
cost2 := 4
costBoth := 15
need1 := 2
need2 := 3
result := minimumCost(cost1, cost2, costBoth, need1, need2)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
def minimum_cost(cost1: int, cost2: int, cost_both: int, need1: int, need2: int) -> int:
# 各买各的
res1 = cost1 * need1 + cost2 * need2
# 确保 need1 <= need2 以便混合策略计算
if need1 > need2:
need1, need2 = need2, need1
cost2 = cost1 # 注意：交换后 cost2 需要同步更新
# 全买双人票
res2 = cost_both * need2
# 混合策略：部分买双人票，部分买单人票
res3 = cost_both * need1 + cost2 * (need2 - need1)
return min(res1, res2, res3)
def main():
cost1 = 5
cost2 = 4
cost_both = 15
need1 = 2
need2 = 3
result = minimum_cost(cost1, cost2, cost_both, need1, need2)
print(result)if __name__ == "__main__":
main()
C++完整代码如下：
using namespace std;
long long minimumCost(int cost1, int cost2, int costBoth, int need1, int need2) {
// 各买各的
long long res1 = 1LL * cost1 * need1 + 1LL * cost2 * need2;
// 确保 need1 <= need2 以便混合策略计算
if (need1 > need2) {
swap(need1, need2);
cost2 = cost1;
}
// 全买双人票
long long res2 = 1LL * costBoth * need2;
// 混合策略：部分买双人票，部分买单人票
long long res3 = 1LL * costBoth * need1 + 1LL * cost2 * (need2 - need1);
return min({res1, res2, res3});
}
int main() {
int cost1 = 5;
int cost2 = 4;
int costBoth = 15;
int need1 = 2;
int need2 = 3;
long long result = minimumCost(cost1, cost2, costBoth, need1, need2);
cout << result << endl;return0;
}
我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
