讨厌鬼进货

思路

这道题乍一看有三种进货方式，感觉挺复杂？别急，咱们理一下：

  • 每种货物可以从供应商 1 买，花 a[i]
  • 也可以从供应商 2 买，花 b[i]
  • 还有个网购平台，花 c 元一次性买齐所有 n 种

那问题来了——如果不用网购平台，怎么买最便宜？是不是每种货物都挑两个供应商里便宜的那个就行了？对，就是 min(a[i], b[i]) 逐个取最小值，然后加起来。

那网购平台呢？它是一口价 c 元买齐全部，不能拆分。所以要么全用网购，要么完全不用网购、每种货物自己从供应商里挑。

> 等等，能不能"部分从供应商买 + 网购也买"混着来？

可以混着来，但你想想：网购已经花了 c 元把所有东西都买了，再从供应商买就是浪费钱。所以最优方案一定是二选一——要么纯供应商方案，要么纯网购方案。

最终答案就是两种方案取最小值：。

具体步骤

  1. 读入 n、c 和两个数组 a、b
  2. 遍历每种货物，累加 min(a[i], b[i])
  3. 拿累加结果和 c 比较，输出较小的那个

代码

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n, c;
    cin >> n >> c;

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

    cout << min(sum, (long long)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();
        int c = sc.nextInt();

        int[] a = new int[n];
        int[] b = new int[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        for (int i = 0; i < n; i++) b[i] = sc.nextInt();

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

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

n, c = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
s = sum(min(x, y) for x, y in zip(a, b))
print(min(s, c))

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const [n, c] = lines[0].split(' ').map(Number);
    const a = lines[1].split(' ').map(Number);
    const b = lines[2].split(' ').map(Number);
    let sum = 0;
    for (let i = 0; i < n; i++) {
        sum += Math.min(a[i], b[i]);
    }
    console.log(Math.min(sum, c));
});

复杂度分析

  • 时间复杂度: ，遍历一次数组
  • 空间复杂度: ，存储两个数组

总结

这题本质上就是个贪心：先算出供应商方案的最优成本（每种货物哪家便宜买哪家），再和网购一口价比一比，取小的就完了。关键是想清楚"网购和供应商混合购买"不会比两个纯方案更优，因为网购没法拆分，用了就是全买。典型的"想清楚就三行核心代码"的贪心入门题。