题目链接

小红的魔法药剂

题目描述

小红需要 个不同的魔法药剂。对于第 种药剂：

  • 可以从商店以 的价格购买红色版本
  • 也可以用两种其他的红色版本药剂配置成蓝色版本

小红想知道，她最少需要花多少钱才能得到 1 到 个不同的魔法药剂（蓝色或红色都可以）。

输入:

  • 第一行输入一个整数 ，表示魔法药剂数量
  • 第二行输入 个整数 ，表示第 种红色版本魔法药剂的价格
  • 接下来 行，每行两个整数 和 ，表示用第 种和第 种红色版本魔法药剂配置第 种蓝色版本魔法药剂

输出:

  • 一个整数，表示最少需要的花费

解题思路

这是一个贪心问题，可以通过以下步骤解决：

  1. 关键发现：

    • 对于每种药剂，我们只需要考虑两种方案：
      • 直接购买红色版本，花费
      • 用其他两种红色药剂配置蓝色版本，花费
    • 选择这两种方案中花费较小的即可

  2. 贪心策略：

    • 对于第 i 种药剂，比较：
      • 直接购买的花费
      • 配置的花费 （u和v是配方中指定的两种药剂）
    • 选择较小值作为获得这种药剂的花费

  3. 具体步骤：

    • 读入所有药剂的价格和配方
    • 遍历每种药剂，计算获得该药剂的最小花费
    • 将所有药剂的最小花费相加得到答案

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int u, v;
        cin >> u >> v;
        ans += min(a[i], a[u] + a[v]);
    }
    cout << ans << endl;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int[] a = new int[n + 1];
        for(int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
        }
        
        int ans = 0;
        for(int i = 1; i <= n; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            ans += Math.min(a[i], a[u] + a[v]);
        }
        
        System.out.println(ans);
    }
}

n = int(input())
a = [0] + list(map(int, input().split()))  # 1-based indexing

ans = 0
for i in range(1, n + 1):
    u, v = map(int, input().split())
    ans += min(a[i], a[u] + a[v])

print(ans)

算法及复杂度

  • 算法：贪心算法
  • 时间复杂度： - 只需要遍历一次所有药剂
  • 空间复杂度： - 需要存储所有药剂的价格