首页 > 试题广场 >

小红的魔法药剂

[编程题]小红的魔法药剂

热度指数：2600 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 小红打算收集编号为 $1\sim n$ 的 $n$ 种魔法药剂，其中每种药剂有两种形态：红色版本与蓝色版本。

$\hspace{15pt}$ 获得药剂的方式如下：
$\hspace{23pt}\bullet\,$ 直接购买：购买一瓶第 $i$ 种红色版本药剂需要花费 $a_i$ 金币；
$\hspace{23pt}\bullet\,$ 调配合成：若已拥有红色版本的第 $b_i$ 种与第 $c_i$ 种药剂，可分别消耗一瓶，调配得到蓝色版本的第 $i$ 种药剂，调配本身不额外花费金币（仅需保证两种原料存在）。

$\hspace{15pt}$ 小红不关心颜色，只要求最终至少拥有 $1\sim n$ 每种药剂中的任意一种形态（红或蓝）。请计算她所需支付的最小总金币数。

输入描述:

第一行输入一个整数 ，表示药剂种类数量。
第二行输入  个整数 ，依次表示直接购买一瓶第  种红色药剂的价格。
接下来  行，第  行输入两个整数 ，表示合成蓝色版本第  种药剂所需的两种红色药剂的编号。

输出描述:

输出一个整数，表示获得  种不同药剂所需支付的最小金币数。

示例1

输入

输出

说明

一种最优方案：
 直接购买第  种红色药剂，花费 ；
 利用红色的  调配得到第  种蓝色药剂，花费 ；
最终花费 ，满足拥有  的不同药剂。

算法知识视频讲解

神崎兰子

发表于 2025-10-24 15:40:13

精华题解小红收集魔法药剂 - 题解题意精炼有种药剂，每种药剂有「红」「蓝」两种形态：直接购买：第种红色药剂单价为。调配合成：若已有「红色」的第、第种药剂，各消耗一瓶，可合成「蓝色」的第种，合成本身不额外花费金币。目标：使得最终对每个编号至少拥有该药剂的任意一种形态（红或展开全文

星图史话

发表于 2025-10-24 09:22:28

//***只要你目光是瞄准月亮迷失过又有何妨***// #include<bits/stdc++.h> using namespace std; using ll=long long; int n; const int N=1e5; ll fac[N]; int a[N]; int 展开全文

BraveCoder

发表于 2025-09-04 09:09:51

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n 展开全文

牛客394342993号

发表于 2025-10-24 23:09:24

void solve() { int n; cin >> n; V<int> a(n + 1, 0); FOR(i, 1, n) cin >> a[i]; int ans = accumulate(ALL(a), 0ll) 展开全文

Xiaotu666

发表于 2025-10-24 10:34:01

#include<bits/stdc++.h> using namespace std; int a[100010],b[100010],c[100010],s[100010]; int main(){ int n; cin>>n; for(int i 展开全文

bing糖雪狸

发表于 2025-10-24 17:59:57

解题思路核心思想这道题的关键是理解：对于每种药剂，我们需要独立决定是获得红色版本还是蓝色版本。对于第 i 种药剂，有两种选择：选择红色版本：成本为 cost[i] 选择蓝色版本：成本为 cost[b_i] + cost[c_i] 这里需要注意的是：合成蓝色药剂的成本是购买两种红色原料的成展开全文

lahm66

发表于 2025-09-23 21:19:05

贪心，不需要考虑太多第i时选择红色，或使用红色合成蓝色，取最小。不需要考虑前面买了红色后面可以接着用，按题目意思是每种只能使用一次。 import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main 展开全文

牛客473425803号

发表于 2025-11-29 16:12:49

#include <iostream> using namespace std; int main() { int n; cin>>n; int a[100000]; int cost=0; for(int i=1;i<=n;i 展开全文

红豆香芋派

发表于 2025-10-24 14:23:55

Golang实现 package main import ( "fmt" ) func main() { var n, b, c int var a[]int ans := 0 solve := func () int { 展开全文

nameofworld

发表于 2025-09-16 11:03:29

#include <iostream> using namespace std; int main() { int n; cin>>n; int a[n],b[n],c[n]; for(int i=0;i<n;i++){ 展开全文

拒绝无效加班的牛油果很认真

发表于 2025-10-24 17:27:39

题解：小红的魔法药剂（贪心策略）题目大意小红想要收集编号从到的种魔法药剂，每种药剂有两种形态：红色版本和蓝色版本。她只需要每种药剂拥有任意一种形态即可。获取方式有两种：直接购买红色药剂：第种红色药剂花费金币。调配合成蓝色药剂：若已拥有红色的第和第种药剂展开全文

问题信息

贪心

难度：

14条回答 12收藏 281浏览

小红的魔法药剂

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题