BISHI46　小红的魔法药剂¶

简单通过率 63.91%python3样例通过牛客 AC贪心

牛客原题　源码

讲解章节：贪心

一句话

每种药剂要么直接买红色，要么买两瓶红色合成蓝色。

解题思路¶

这题考什么¶

看着像图论/依赖关系，其实各种药剂互相独立：

合成第 i 种蓝色药剂需要消耗一瓶红色 b_i 和一瓶红色 c_i，而这两瓶是「额外买来专门消耗掉的」，消耗完就没了，不能同时充当「我拥有第 b_i 种药剂」的那一瓶；
但红色药剂可以随便买任意多瓶，所以为第 i 种药剂做决策时完全不影响别的药剂的决策。

于是每种药剂的最小花费就是

min(a_i, a_{b_i} + a_{c_i})，

答案 = Σ_i min(a_i, a_{b_i} + a_{c_i})。

验算样例：a = [2,4,10,1,3] i=1: min(2, a2+a3=14) = 2 i=2: min(4, a4+a5=4) = 4 i=3: min(10, a1+a2=6) = 6 i=4: min(1, a2+a5=7) = 1 i=5: min(3, a1+a4=3) = 3 合计 16 ✓（与题面给的方案花费一致）。

数据规模与复杂度¶

n <= 1e5，a_i <= 1e4。O(n) 一遍即可。答案上界 1e5 * 2e4 = 2e9，超过 32 位 int，C/C++ 要 long long。

坑在哪¶

合成的原料是消耗品，不能「一瓶两用」，所以不存在「买一瓶红 1 既满足第 1 种又当第 3 种的原料」这种省钱操作；正因如此各项才独立，才不需要做图上的 DP；
b_i、c_i 可能等于 i 自己，也可能 b_i == c_i（题面只保证 1<=b,c<=n），此时公式仍然成立（要买两瓶同种红色，花 2*a_{b_i}）；
每行两个数共 n 行，整块读入按游标取最快；
合成得到的是蓝色第 i 种，而题目只要求「每种药剂有任意一种形态」，所以合成出的蓝色确实顶得上一瓶。若题目要求的是红色，这题就完全不同了。

贪心的一般套路见 47-贪心。

参考实现¶

solutions/BISHI46.py
import sys


def main() -> None:
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = [int(v) for v in data[1:n + 1]]
    p = n + 1                       # 游标：n 行配方从这里开始，每行占 2 个整数
    total = 0
    for i in range(n):
        b = int(data[p]) - 1        # 题目编号从 1 开始，转成 0 基下标
        c = int(data[p + 1]) - 1
        p += 2
        # 直接买红色，或者买两瓶原料合成蓝色，取便宜的
        cost = a[b] + a[c]          # b == c 时就是买两瓶同种，公式照样成立
        total += a[i] if a[i] < cost else cost
    print(total)


main()

BISHI46 小红的魔法药剂¶