小红的魔法药剂

思路

题目在说什么？有 种魔法药剂，每种药剂有红色和蓝色两种形态。你需要让每种药剂至少拥有一种形态。获得方式有两种：

  1. 直接购买红色药剂 ，花费 金币
  2. 合成蓝色药剂 ：消耗各一瓶红色药剂 和 （不额外花费，但原料被消耗）

问最少花多少金币？

关键观察

注意到合成蓝色药剂 需要消耗红色药剂 和 。这意味着如果你要用红色药剂 去做合成的原料，你需要额外买一份，和你自己留着用的那份是独立的。

换句话说，每次合成都是独立事件——需要专门为它购买原料，不存在"一份红色药剂既当原料又当收藏品"的情况。

那么对于每种药剂 ，我们就有两个独立的选择：

  • 选红色：直接买，花
  • 选蓝色：买 和 做原料合成，花

因为每种药剂的决策互不影响（合成消耗的是新买的原料），所以每种药剂独立取最小值就好了。

举个例子

以样例为例，，价格为 ：

药剂 买红色 合成蓝色 最优
1 2 4+10=14 买红色，花2
2 4 1+3=4 都一样，花4
3 10 2+4=6 合成蓝色，花6
4 1 4+3=7 买红色，花1
5 3 2+1=3 都一样，花3

总计 ，和答案吻合。

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    vector<long long> p(n);
    for(int i=0;i<n;i++) scanf("%lld",&p[i]);
    long long ans=0;
    for(int i=0;i<n;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        a--;b--;
        ans += min(p[i], p[a]+p[b]);
    }
    printf("%lld\n",ans);
    return 0;
}

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] p = new long[n];
        for (int i = 0; i < n; i++) p[i] = sc.nextLong();
        long ans = 0;
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt() - 1;
            int b = sc.nextInt() - 1;
            ans += Math.min(p[i], p[a] + p[b]);
        }
        System.out.println(ans);
    }
}

import sys
input = sys.stdin.readline

n = int(input())
p = list(map(int, input().split()))
ans = 0
for i in range(n):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    ans += min(p[i], p[a] + p[b])
print(ans)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const p = lines[1].split(' ').map(Number);
    let ans = 0;
    for (let i = 0; i < n; i++) {
        const [a, b] = lines[2 + i].split(' ').map(Number);
        ans += Math.min(p[i], p[a - 1] + p[b - 1]);
    }
    console.log(ans);
});

复杂度分析

  • 时间复杂度：，读入加一轮遍历
  • 空间复杂度：，存储价格数组

总结

这道题看起来像图论或者复杂的贪心，但抓住"合成消耗原料"这个关键点后就豁然开朗了：每次合成都是独立买原料，所以每种药剂的选择（买红色 vs 合成蓝色）互不干扰，逐个取 即可。典型的"看着复杂实则简单"的贪心题。