首页 > 试题广场 >

小红的魔法药剂

[编程题]小红的魔法药剂
  • 热度指数：2591 时间限制：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 每种药剂中的任意一种形态（红或蓝）。请计算她所需支付的最小总金币数。

输入描述:
\hspace{15pt}第一行输入一个整数 n\left(1\leqq n\leqq 10^5\right)，表示药剂种类数量。
\hspace{15pt}第二行输入 n 个整数 a_1,a_2,\dots,a_n\left(1\leqq a_i\leqq 10^4\right)，依次表示直接购买一瓶第 i 种红色药剂的价格。
\hspace{15pt}接下来 n 行，第 i 行输入两个整数 b_i,c_i\left(1\leqq b_i,c_i\leqq n\right)，表示合成蓝色版本第 i 种药剂所需的两种红色药剂的编号。


输出描述:
\hspace{15pt}输出一个整数，表示获得 n 种不同药剂所需支付的最小金币数。
示例1

输入

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

输出

16

说明

\hspace{15pt}一种最优方案：
\hspace{23pt}\bullet\, 直接购买第 1,2,4,5 种红色药剂，花费 2+4+1+3=10；
\hspace{23pt}\bullet\, 利用红色的 1,2 调配得到第 3 种蓝色药剂，花费 2+4=6；
\hspace{15pt}最终花费 10+6=16，满足拥有 1\sim5 的不同药剂。
算法知识视频讲解
添加回答
圣Y圣头像 圣Y圣
想复杂了，就想着两种合成一种，还能再合成，比较得到价格最便宜的为止。
结果合成的是蓝色药剂，没法二次合成了。
发表于 2025-08-16 00:20:39 回复(0)
Java
BraveCoder头像 BraveCoder 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();

        String[] redMedStr = in.nextLine().split(" ");
        int[] redMeds = new int[redMedStr.length];
        for (int i = 0; i < redMeds.length; i++) {
            redMeds[i] = Integer.parseInt(redMedStr[i]);
        }

        int sum = 0;
        for (int i = 0; i < n; i++) {
            int b = in.nextInt();
            int c = in.nextInt();
            int blueMed =  redMeds[b-1] + redMeds[c-1];
            int redMed = redMeds[i];
            sum += Math.min(blueMed, redMed);
        }
        System.out.println(sum);
    }
}

发表于 2025-09-04 09:09:24 回复(3)
草海桐头像 草海桐
合成的是蓝色的，不能用于后续的合成，所以直接比较直接购买的价格和合成的价格就行
发表于 2025-09-02 16:54:01 回复(0)
Hero_123头像 Hero_123
感觉看不懂中文了，意思很绕，不好明白题目在说什么
发表于 2025-12-10 15:26:45 回复(1)
方对此无效莫斯科头像 方对此无效莫斯科 
?

发表于 2025-10-24 20:15:37 回复(0)
DrakUmr头像 DrakUmr
写了会dp，结果发现不能继续合成，感觉可以出道新题可以继续合成那种
发表于 2025-10-24 19:30:55 回复(0)
C++
Yeceng头像 Yeceng
#include<iostream>
#include<vector>
using namespace std;
class price
{
public:
int r_price;
int hecheng[2];
};
int getallprice(vector<price> all,int n)
{
int allprice=0;
for(vector<price>::iterator it=all.begin();it!=all.end();it++)
{
if(all[it->hecheng[0]-1].r_price+all[it->hecheng[1]-1].r_price<it->r_price)
{
allprice+=all[it->hecheng[0]-1].r_price+all[it->hecheng[1]-1].r_price;
}
else allprice+=it->r_price;
}
return allprice;
}
int main()
{
int n;cin>>n;
vector<price> all;
for(int i =1;i<=n;i++)
{
price p;cin>>p.r_price;
all.push_back(p);
}
for(vector<price>::iterator it=all.begin();it!=all.end();it++)
{
cin>>it->hecheng[0]>>it->hecheng[1];
}
cout<<getallprice(all,n)<<endl;
return 0;
}通过了各位大神 但是我感觉我写出来的代码总是很复杂 有没有大佬指点一下在哪些方面能精简一些

发表于 2025-10-24 19:09:52 回复(0)
Python 3
牛客83749222号头像 牛客83749222号
n=int(input())
a=list(map(int,input().split()))
b1,c1=[],[]
for __ in range(n):
    b,c=list(map(int,input().split()))
    b1.append(b)
    c1.append(c)
s,s1=0,0
for i in range(n):
    c0=a[b1[i]-1]+a[c1[i]-1]
    s+=min(c0,a[i])
    s1+=a[i]
print(min(s,s1))

发表于 2025-10-24 12:10:39 回复(0)
牛客341639822号头像 牛客341639822号 
''' 注意：调配后的试剂颜色为蓝色不能再使用 若调配的价格更低，直接使用调配的价格替换原列表中红色实际价格，得出的结果更小 因为替换后的蓝色试剂价格可能会被再次引用，来计算调配价格，但因时蓝色试剂，故不能再被引用 故需要再新建列表用来存储调配后的价格，再比较两个列表，进而获取最小值 '''  n = int(input())
red = [int(x) for x in input().split()]
blue = []
result = 0 for i in range(n):
    b, c = map(int, input().split())
    blue.append(red[b-1] + red[c-1]) for i in range(n):
    result += min(blue[i],red[i]) print(result)
发表于 2025-10-04 11:47:41 回复(0)
精致的熊熊在努力存钱头像 精致的熊熊在努力存钱
n = int(input())
a_li = list(map(int,input().split()))
b_li = []
for i in range(n):
    a,b = map(int,input().split())
    money_b = a_li[a-1]+a_li[b-1]
    b_li.append(money_b)
min_money = []
for j in range(n):
    min_money.append(min(a_li[j],b_li[j]))
print(sum(min_money))
发表于 2025-10-03 20:52:50 回复(0)
Java
牛客916838684号头像 牛客916838684号
最笨办法 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int[] prr = new int[n];

        int count =0;
        
        for(int i=0; i<n; i++){
            prr[i] = in.nextInt();

        }

        int[] prb = new int[n];
        for( int i =0; i<n; i++){
            prb[i] = prr[in.nextInt()-1] + prr[in.nextInt()-1];
            // System.out.println(prb[i]);
        }

        for(int i=0; i<n; i++){
            if(prr[i] < prb[i]){
                count = count +prr[i];// 直接购买
            }else{
                count = count + prb[i];//合成
            }
        }
        System.out.println(count);

        

    }
}


发表于 2025-09-29 08:38:27 回复(0)
牛客223294923号头像 牛客223294923号
答案是不是有问题？几个算法都直接用合成和直接购买去计算更小值并加到总和。
我的疑惑是，比如药剂3可由药剂1，2合成。假设说药剂3购买价格是10，药剂1购买价格是1，药剂2购买价格是2。
 合成显然比购买花费低，但是合成的药剂3是蓝色的，不可用于后续合成，而购买的药剂3是红色的，可用于后续合成。 如果购买虽然花费高，但它后续去合成别的药剂带来的价值更大呢？
发表于 2025-08-25 20:25:59 回复(3)
牛客847294653号头像 牛客847294653号
想复杂了，寻思着能一直合成来着
n = int(input())
a = list(map(int,input().split()))
bc = [list(map(int,input().split())) for _ in range(n)]
while 1:
    tmpa = a.copy()
    for i in range(n):
        tmpa[i] = min(a[bc[i][0]-1] + a[bc[i][1]-1],a[i])
    if tmpa == a:
        break
    else:
        a = tmpa
print(sum(a))
发表于 2025-08-25 15:53:09 回复(0)
Python 3
牛客113445882号头像 牛客113445882号
n = int(input().strip())
a = list(map(int,input().split()))
sum = 0
for i in range(n):
    x, y = list(map(int, input().split()))
    c = min((a[x-1]+a[y-1]),a[i])
    sum += c
print(sum)
发表于 2025-06-22 14:46:50 回复(0)
提交观点

问题信息

贪心
难度：
14条回答 278浏览

热门推荐

相关试题

小红的魔法药剂

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号