题解 | #讨厌鬼进货#

题目链接

讨厌鬼进货

题目描述

讨厌鬼需要采购 $n$ 种货物，每种货物都至少要购买一件。对于第 $i$ 种货物，她有两种独立的购买方式：

从供应商A处以 $a_i$ 元的价格购买。
从供应商B处以 $b_i$ 元的价格购买。

此外，还有第三种打包购买方式： 3. 在网购平台一次性购买全部 $n$ 种货物，总花费为 $C$ 元。

可以自由组合以上方式，求满足每种货物都至少有一件的最小总花费。

解题思路

这是一个典型的决策问题，我们需要在两种主要的采购策略中选择花费更小的一种。

策略一：完全不使用网购平台

在这种策略下，我们完全放弃网购平台的打包优惠。对于需要的每一种货物 $i$ （从1到 $n$ ），我们都必须独立购买。为了使花费最小，我们应该为每种货物选择价格更低的供应商。

对于第 $i$ 种货物，其最低采购成本是 $\min(a_i, b_i)$ 。
要买齐所有 $n$ 种货物，总花费就是将每种货物的最低成本相加。
因此，策略一的总花费为： $S = \sum_{i=1}^{n} \min(a_i, b_i)$ 。

策略二：使用网购平台

网购平台提供了一个“一键购齐”的选项，花费为 $C$ 元。这个选项不能拆分，要么买全部，要么不买。

最终决策

问题的核心就在于比较这两种策略的总花费。

如果我们选择策略一，总花费是 $S$ 。
如果我们选择策略二，总花费是 $C$ 。

为了实现最小总花费，我们只需要在这两个最终的总花费中选择一个较小的值即可。

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

算法步骤

读取货物种类数 $n$ 和网购平台价格 $C$ 。
读取供应商A的 $n$ 个价格 $a_1, a_2, \dots, a_n$ 。
读取供应商B的 $n$ 个价格 $b_1, b_2, \dots, b_n$ 。
初始化一个变量 sum_of_mins 为 0。
遍历从 $0$ 到 $n-1$ 的所有货物，对于每种货物 $i$ ：
- 计算 $\min(a_i, b_i)$ 。
- 将这个最小值累加到 sum_of_mins 上。
比较 sum_of_mins 和 $C$ ，输出两者中的较小值。

代码

c++
java
python

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

using namespace std;

int main() {
    ios_base::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 sum_of_mins = 0;
    for (int i = 0; i < n; ++i) {
        sum_of_mins += min(a[i], b[i]);
    }
    
    cout << min(sum_of_mins, c) << 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);
        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 sumOfMins = 0;
        for (int i = 0; i < n; i++) {
            sumOfMins += Math.min(a[i], b[i]);
        }
        
        System.out.println(Math.min(sumOfMins, c));
    }
}

import sys

def solve():
    n, c = map(int, sys.stdin.readline().split())
    a = list(map(int, sys.stdin.readline().split()))
    b = list(map(int, sys.stdin.readline().split()))
    
    sum_of_mins = 0
    for i in range(n):
        sum_of_mins += min(a[i], b[i])
        
    print(min(sum_of_mins, c))

solve()

算法及复杂度

算法：模拟/贪心
时间复杂度：我们需要遍历一次所有 $n$ 种货物，来计算独立采购的总成本。因此，总时间复杂度为 $\mathcal{O}(n)$ 。
空间复杂度：我们需要存储两家供应商的价格列表。因此，空间复杂度为 $\mathcal{O}(n)$ 。