题解 | #讨厌鬼进货#

题目链接

讨厌鬼进货

题目描述

需要采购 $n$ 种货物。每种货物 $i$ 的获取方式如下：

在供应商 A 处以 $a_i$ 元购得。
在供应商 B 处以 $b_i$ 元购得。

此外，还有一个总包选项：

在网购平台一次性购买全部 $n$ 种货物，总花费为 $c$ 元。

可以自由组合以上方式，只要保证最终每种货物都至少购买一件即可。求完成采购的最小总花费。

解题思路

本题是一个简单的决策问题。我们需要找到成本最低的采购方案。我们可以将所有可能的采购策略归结为两大类进行比较。

策略一：不使用网购平台 在这种情况下，我们必须为每一种货物单独做决策。对于第 $i$ 种货物，我们有两个选择：从供应商 A 购买或从供应商 B 购买。为了使成本最低，我们显然应该选择价格更便宜的那个供应商。
- 第 $i$ 种货物的最低成本为 $\min(a_i, b_i)$ 。
- 因此，完全不使用网购平台时的总成本，就是将这 $n$ 种货物的最低单价全部相加： $\sum_{i=1}^{n} \min(a_i, b_i)$ 。
策略二：使用网购平台 网购平台提供了一个“一揽子”方案，花费固定为 $c$ 元即可购得所有 $n$ 种货物。

最终决策 我们需要做的就是在以上两种策略的总成本中，选择一个较小的值。

最终的最小总花费 = $\min(\sum_{i=1}^{n} \min(a_i, b_i), c)$

实现要点

在实现时，我们需要遍历所有货物，累加每种货物的最低单价，得到策略一的总成本。
然后将这个总成本与策略二的成本 $c$ 进行比较，取较小者即为答案。
由于货物数量 $n$ 和单价都可能较大，累加的总成本可能会超过32位整数的范围，因此需要使用64位整型（long long 或 long）来存储总花费，以避免溢出。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    long long c;
    cin >> n >> c;

    vector<long long> a(n), b(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> b[i];
    }

    long long individual_cost_sum = 0;
    for (int i = 0; i < n; ++i) {
        individual_cost_sum += min(a[i], b[i]);
    }

    cout << min(individual_cost_sum, c) << 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();
        long c = sc.nextLong();

        long[] a = new long[n];
        long[] b = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
        }
        for (int i = 0; i < n; i++) {
            b[i] = sc.nextLong();
        }

        long individualCostSum = 0;
        for (int i = 0; i < n; i++) {
            individualCostSum += Math.min(a[i], b[i]);
        }

        System.out.println(Math.min(individualCostSum, c));
    }
}

n, c = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

individual_cost_sum = 0
for i in range(n):
    individual_cost_sum += min(a[i], b[i])

print(min(individual_cost_sum, c))

算法及复杂度

算法：贪心
时间复杂度：我们需要遍历一次包含 $n$ 个元素的数组来计算最低单价之和，因此时间复杂度为 $\mathcal{O}(n)$ 。
空间复杂度：需要存储两个包含 $n$ 个价格的数组，因此空间复杂度为 $\mathcal{O}(n)$ 。