首页 > 试题广场 >

小红的魔法药剂

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

输入描述:
\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 的不同药剂。
算法知识视频讲解
添加回答
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)
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)
提交观点

问题信息

贪心
难度：
2条回答 285浏览

热门推荐

相关试题

小红的魔法药剂

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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