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

题目链接

小红的魔法药剂

题目描述

小红需要集齐 $n$ 种魔法药剂（编号1到 $n$ ）。对于每种药剂，她只需要拥有红色或蓝色版本中的任意一种即可。

获取药剂的方式有两种：

直接购买：花费 $c_i$ 金币购买第 $i$ 种药剂的红色版本。
调配合成：如果已经拥有第 $u$ 种和第 $v$ 种药剂的红色版本，就可以免费调配出第 $i$ 种药剂的蓝色版本。

给定每种红色药剂的价格以及每种蓝色药剂的合成配方，请计算集齐所有 $n$ 种药剂的最小总金币数。

解题思路

这是一个典型的决策优化问题。我们需要为每一种药剂（从1到 $n$ ）决定如何获取它，以使得总花费最小。

核心思想：独立决策

关键的洞察在于，获取第 $i$ 种药剂的决策，与其他药剂（如第 $j$ 种）的最终获取方式是相互独立的。我们只需要为每一种药剂单独计算出其最低的获取成本，然后将所有这些最低成本相加，就是最终的答案。

分析每种药剂的最低成本

对于第 $i$ 种药剂，我们有两种获取它的方式，需要比较它们的成本：

方式一：直接购买红色版本
- 这种方式的成本是固定的，就是题目给出的价格 $c_i$ 。
方式二：调配合成蓝色版本
- 根据题目，合成蓝色版本的第 $i$ 种药剂，需要拥有红色版本的原料药剂 $u$ 和 $v$ 。
- 要拥有红色版本的原料，我们必须通过直接购买的方式获得它们。
- 因此，通过合成方式获得第 $i$ 种药剂的成本，就是购买其两种红色原料的成本之和： $c_u + c_v$ 。

最终决策

对于第 $i$ 种药剂，其最低获取成本就是以上两种方式成本的较小值： min_cost_for_potion_i = $\min(c_i, c_u + c_v)$

我们的总策略就是对每一种药剂都进行这样的计算，然后求和。

算法步骤

读取 $n$ 以及所有 $n$ 种红色药剂的价格 $c_1, c_2, \dots, c_n$ 。
初始化一个总花费 total_cost 为0。
循环 $n$ 次，在第 $i$ 次循环中处理第 $i+1$ 种药剂：
- 读取合成第 $i+1$ 种药剂所需的两种原料的编号 $u$ 和 $v$ 。
- 获取直接购买的成本 direct_cost = $c_{i+1}$ 。
- 计算合成的成本 synth_cost = $c_u + c_v$ 。
- 找出这两种成本的较小值 min(direct_cost, synth_cost)。
- 将这个较小值累加到 total_cost 上。
循环结束后，total_cost 就是所需的最小总金币数。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    int n;
    cin >> n;

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

    long long total_cost = 0;
    for (int i = 1; i <= n; ++i) {
        int u, v;
        cin >> u >> v;

        long long direct_cost = prices[i];
        long long synth_cost = prices[u] + prices[v];

        total_cost += min(direct_cost, synth_cost);
    }

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

        long totalCost = 0;
        for (int i = 1; i <= n; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();

            long directCost = prices[i];
            long synthCost = prices[u] + prices[v];

            totalCost += Math.min(directCost, synthCost);
        }

        System.out.println(totalCost);
    }
}

import sys

def solve():
    n = int(sys.stdin.readline())
    # 0-indexed prices, prices[i] is cost for potion i+1
    prices = list(map(int, sys.stdin.readline().split()))
    
    total_cost = 0
    for i in range(n):
        # Recipe for potion i+1
        u, v = map(int, sys.stdin.readline().split())
        
        # Direct purchase cost for potion i+1
        direct_cost = prices[i]
        
        # Synthesis cost needs red ingredients u and v
        # Potion u is at index u-1, potion v is at index v-1
        synth_cost = prices[u - 1] + prices[v - 1]
        
        total_cost += min(direct_cost, synth_cost)
        
    print(total_cost)

solve()

算法及复杂度

算法：贪心
时间复杂度：我们需要读取 $n$ 个价格和 $n$ 组配方，并在一个循环中处理它们。循环体内的操作是常数时间的。因此，总时间复杂度为 $\mathcal{O}(n)$ 。
空间复杂度：我们需要一个数组或列表来存储 $n$ 种药剂的价格。因此，空间复杂度为 $\mathcal{O}(n)$ 。