题解 | #小红的魔法药剂#

题目链接

小红的魔法药剂

题目描述

小红需要 $n$ 种不同的魔法药剂。

她可以花 $c_i$ 的价格购买第 $i$ 种红色版本的魔法药剂。

她也可以用第 $u$ 种和第 $v$ 种红色版本的药剂来配置出第 $i$ 种蓝色版本的药剂。

小红想知道，她最少需要花多少钱才能得到从 1 到 $n$ 所有种类的魔法药剂（红色或蓝色均可）。

解题思路

这是一个典型的贪心问题，其核心在于每个决策都是独立的。

对于 $1$ 到 $n$ 的每一种魔法药剂 $i$ ，我们都有两种获取它的方式：

直接购买红色版：成本为 $c_i$ 。
配置蓝色版：成本为 $c_u + c_v$ ，其中 $u$ 和 $v$ 是配置第 $i$ 种药剂所需的两种红色药剂的编号。

关键在于，为某一种药剂做出选择（是购买还是配置）并不会影响到其他任何药剂的获取成本。所有红色药剂的原始价格 $c_i$ 是固定不变的。

因此，我们可以对每一种药剂都独立地做出最优选择。对于第 $i$ 种药剂，我们只需简单地比较直接购买和配置两种方式的成本，然后选择其中较小的一个即可。

第 $i$ 种药剂的最小成本为 $\min(c_i, c_u + c_v)$ 。

总的最小花费就是将这 $n$ 种药剂的最小成本全部加起来。

总最小花费 $= \sum_{i=1}^{n} \min(c_i, c_{u_i} + c_{v_i})$ 。

实现上，我们先读入并存储所有红色药剂的价格。然后遍历每一种药剂，计算其最小获取成本，并累加到一个总和变量中。由于总花费可能很大，需要使用64位整型（long long）来防止溢出。

代码

c++
java
python

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<long long> c(n);
    for (int i = 0; i < n; ++i) {
        cin >> c[i];
    }

    long long total_cost = 0;
    for (int i = 0; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        // 成本是 1-indexed，数组是 0-indexed
        long long synthesis_cost = c[u - 1] + c[v - 1];
        long long direct_cost = c[i];
        total_cost += min(direct_cost, synthesis_cost);
    }

    cout << total_cost << 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();
        long[] c = new long[n];
        for (int i = 0; i < n; i++) {
            c[i] = sc.nextLong();
        }

        long totalCost = 0;
        for (int i = 0; i < n; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            // 成本是 1-indexed，数组是 0-indexed
            long synthesisCost = c[u - 1] + c[v - 1];
            long directCost = c[i];
            totalCost += Math.min(directCost, synthesisCost);
        }

        System.out.println(totalCost);
    }
}

import sys

def solve():
    try:
        n_str = sys.stdin.readline()
        if not n_str: return
        n = int(n_str)
        
        c = list(map(int, sys.stdin.readline().split()))
        
        total_cost = 0
        for i in range(n):
            u, v = map(int, sys.stdin.readline().split())
            # 成本是 1-indexed，数组是 0-indexed
            synthesis_cost = c[u - 1] + c[v - 1]
            direct_cost = c[i]
            total_cost += min(direct_cost, synthesis_cost)
            
        print(total_cost)
    except (IOError, ValueError):
        return

solve()

算法及复杂度

算法：贪心算法
时间复杂度: $\mathcal{O}(n)$ 。我们需要一次遍历来读取 $n$ 个红色药剂的价格，另一次遍历来计算每种药剂的最小成本。
空间复杂度: $\mathcal{O}(n)$ 。我们需要一个大小为 $n$ 的数组来存储所有红色药剂的价格。