讨厌鬼进货

[题目链接](https://www.nowcoder.com/practice/be73fed67d1b4bceab9e05959d295e49)

思路

讨厌鬼需要购买 种货物，有三种渠道：供货商 A、供货商 B 和网购。网购是一次性买齐所有 种货物，总价为 。而从 A、B 处购买可以逐件选择，因此对每件货物取 A、B 中的较低价即可。

贪心策略

对于从供货商购买的方案，每种货物独立选择，取 再求和，得到线下最优总价 。

最终答案就是线下最优总价和网购总价的较小值：。

样例演示

5 种货物，网购总价 。

货物 A 价格 B 价格 取最小
1 2 1 1
2 1 2 1
3 2 1 1
4 1 2 1
5 2 3 2

线下总价 ，网购总价 ，答案 。

复杂度

  • 时间复杂度：，遍历一次数组即可。
  • 空间复杂度：，存储两个价格数组。

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, p;
    scanf("%d%d", &n, &p);
    vector<int> a(n), b(n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    for(int i=0;i<n;i++) scanf("%d",&b[i]);
    long long sum = 0;
    for(int i=0;i<n;i++) sum += min(a[i], b[i]);
    printf("%lld\n", min(sum, (long long)p));
    return 0;
}

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), p = sc.nextInt();
        int[] a = new int[n], 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, (long) p));
    }
}

import sys
input = sys.stdin.readline
n, p = 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, p))

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const [n, p] = 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, p));
});