题目链接

讨厌鬼进货

题目描述

讨厌鬼需要购买 种货物。他有三种购买方式：

  1. 从供应商 A 处购买，第 件货物的价格为 。
  2. 从供应商 B 处购买，第 件货物的价格为 。
  3. 在京东一次性网购所有 种货物，总价格为 。

讨厌鬼可以自由地为每一件货物选择供应商 A 或 B，也可以选择直接网购所有货物。目标是花最少的钱买齐这 种货物。

解题思路

这是一个简单的决策优化问题。我们需要计算出两种主要采购策略下的总成本，然后取其中的较小值。

策略一：逐件分散采购

在这种策略下，我们不考虑网购。对于每一件货物 （），我们都有两个独立的供应商 A 和 B 可供选择。为了使成本最小化，我们应该为这件货物选择价格更低的供应商。

  • 第 件货物的最低成本为：

将所有 件货物的最低成本相加，就得到了分散采购策略下的总成本：

策略二：整体一次性网购

这种策略的成本是固定的，即网购总价 。

最终决策

要找到买齐所有货物的最少花费，我们只需比较上述两种策略的总成本，然后选择更小的那一个即可。

算法非常直接：首先计算出分散采购的总成本，然后将其与网购总价 比较，输出最小值。

代码

#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 individual_sum = 0;
    for (int i = 0; i < n; ++i) {
        individual_sum += min(a[i], b[i]);
    }

    cout << min(individual_sum, 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 individualSum = 0;
        for (int i = 0; i < n; i++) {
            individualSum += Math.min(a[i], b[i]);
        }

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

import sys

def solve():
    try:
        n, c = map(int, sys.stdin.readline().split())
        a = list(map(int, sys.stdin.readline().split()))
        b = list(map(int, sys.stdin.readline().split()))
    except (IOError, ValueError):
        return

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

solve()

算法及复杂度

  • 算法：贪心

  • 时间复杂度：。

    • 我们需要读取 个价格，这需要 的时间。
    • 然后我们遍历一次这 种货物来计算分散采购的总成本，这同样需要 的时间。

  • 空间复杂度：。

    • 需要 的空间来存储两个供应商的价格列表。