小红的魔法药剂

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

思路

小红需要收集 $n$ 种魔法药剂（编号 $1$ 到 $n$ ），每种药剂有两种获取方式：

直接购买红色版本，花费 $a_i$ ；
配置蓝色版本，用第 $x_i$ 种和第 $y_i$ 种红色药剂合成，花费 $a_{x_i} + a_{y_i}$ 。

关键观察：配置蓝色药剂需要额外购买对应的红色原料，不会复用已有的药剂。因此每种药剂的获取成本是独立的，互不影响。

对于第 $i$ 种药剂，取两种方式的较小值即可：

$ $\text{cost}_i = \min(a_i,\; a_{x_i} + a_{y_i})$ $

答案就是所有药剂成本之和：

$ $\text{ans} = \sum_{i=1}^{n} \text{cost}_i$ $

样例演示

红色药剂价格 $[2, 4, 10, 1, 3]$ ，蓝色药剂价格分别为 $[a_2+a_3, a_4+a_5, a_1+a_2, a_2+a_5, a_1+a_4] = [14, 4, 6, 7, 3]$ 。

逐个取最小值： $\min(2,14) + \min(4,4) + \min(10,6) + \min(1,7) + \min(3,3) = 2+4+6+1+3 = 16$ 。

代码

C++
Java
Python3
JavaScript

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

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        long[] a = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = Long.parseLong(st.nextToken());
        }
        long ans = 0;
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine().trim());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            ans += Math.min(a[i], a[x] + a[y]);
        }
        System.out.println(ans);
    }
}

import sys
input = sys.stdin.readline

n = int(input())
a = [0] + list(map(int, input().split()))
ans = 0
for i in range(1, n + 1):
    x, y = map(int, input().split())
    ans += min(a[i], a[x] + a[y])
print(ans)

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 = parseInt(lines[0]);
    const a = [0, ...lines[1].split(' ').map(Number)];
    let ans = 0;
    for (let i = 1; i <= n; i++) {
        const [x, y] = lines[i + 1].split(' ').map(Number);
        ans += Math.min(a[i], a[x] + a[y]);
    }
    console.log(ans);
});

复杂度分析

时间复杂度： $O(n)$ ，读入并处理每种药剂各一次。
空间复杂度： $O(n)$ ，存储价格数组。