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

题解：小红的魔法药剂（贪心策略）

题目大意

小红想要收集编号从 $1$ 到 $n$ 的 $n$ 种魔法药剂，每种药剂有两种形态：红色版本和蓝色版本。她只需要每种药剂拥有任意一种形态即可。

获取方式有两种：

直接购买红色药剂：第 $i$ 种红色药剂花费 $a_i$ 金币。
调配合成蓝色药剂：若已拥有红色的第 $b_i$ 和第 $c_i$ 种药剂，可以消耗这两瓶红色药剂来合成一瓶蓝色的第 $i$ 种药剂，合成过程不额外花钱。

目标是：最小化总金币花费，使得每种药剂至少有一种形态（红或蓝）。

输入输出示例解析

输入：

5 2 4 10 1 3 2 3 4 5 1 2 2 5 1 4

输出：

说明：

可以直接买红色药剂，或者通过合成获得蓝色药剂。对于第 $i$ 种药剂，我们有两种选择：花费 $a_i$ 金币买红色版本；或者不买红色，但为了合成蓝色版本，需要先买红色的 $b_i$ 和 $c_i$ ，合成成本为 $a_{b_i} + a_{c_i}$ 。

观察题目要求：我们只需要每种药剂至少有一个形态。也就是说，对于第 $i$ 种药剂，我们要么买红色，要么合成蓝色，二者选其一。

关键在于：是否可以独立地对每种药剂做决策？

核心思路：贪心策略

我们发现，虽然合成蓝色药剂依赖其他红色药剂，但题目结构是：每个药剂 $i$ 的蓝色版本只能通过红色药剂 $b_i$ 和 $c_i$ 合成。我们可以选择：买红色 $i$ ，或者不买红色 $i$ ，但必须保证红色 $b_i$ 和红色 $c_i$ 被购买（用于合成蓝色 $i$ ）。

但是，如果每个药剂都独立决策“买红”还是“合蓝”，会存在资源复用的问题：比如红色药剂 $j$ 可能被多个合成过程需要。

然而，本题的关键洞察是：我们可以贪心地为每种药剂 $i$ 独立决策：要么花费 $a_i$ 买红色；要么花费 $a_{b_i} + a_{c_i}$ 来支持合成蓝色（即必须买 $b_i$ 和 $c_i$ 的红色）；取两者最小值。

代码实现

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner reader = new Scanner(System.in);

		int n = reader.nextInt();
		int[] arr = new int[n];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = reader.nextInt();
		}
		int[] brr = new int[n];
		for (int i = 0; i < brr.length; i++) {
			int x = reader.nextInt() - 1;
			int y = reader.nextInt() - 1;
			brr[i] = arr[x] + arr[y];
		}

		long cost = 0;
		for (int i = 0; i < brr.length; i++) {
			cost += Math.min(arr[i], brr[i]);
		}
		System.out.println(cost);

		reader.close();
	}

}

总结

项目内容

题目小红的魔法药剂算法贪心

注意事项合成会消耗原料，但贪心在本题数据下仍成立

时间复杂度 $O(n)$

空间复杂度 $O(n)$