首页 > 试题广场 >

小红的魔法药剂

[编程题]小红的魔法药剂

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

输入描述:

第一行输入一个整数 ，表示药剂种类数量。
第二行输入  个整数 ，依次表示直接购买一瓶第  种红色药剂的价格。
接下来  行，第  行输入两个整数 ，表示合成蓝色版本第  种药剂所需的两种红色药剂的编号。

输出描述:

输出一个整数，表示获得  种不同药剂所需支付的最小金币数。

示例1

输入

输出

说明

一种最优方案：
 直接购买第  种红色药剂，花费 ；
 利用红色的  调配得到第  种蓝色药剂，花费 ；
最终花费 ，满足拥有  的不同药剂。

算法知识视频讲解

Java

牛客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)

Java

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)

提交观点

问题信息

贪心

难度：

2条回答 12收藏 282浏览

小红的魔法药剂

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题