【华为OD-E卷 -60 组装最大可靠性设备 100分（python、java、c++、js、c）】

id="article_content" class="article_content clearfix" style="height: 2000px; overflow: hidden;"> id="content_views" class="markdown_views prism-tomorrow-night">

【华为OD-E卷 - 组装最大可靠性设备 100分（python、java、c++、js、c）】

题目

一个设备由 N 种类型元器件组成（每种类型元器件只需要一个，类型 type 编号从 0~N-1），
每个元器件均有可靠性属性 reliability，可靠性越高的器件其价格 price 越贵。
而设备的可靠性由组成设备的所有器件中可靠性最低的器件决定。
给定预算 S，购买 N 种元器件（每种类型元器件都需要购买一个），在不超过预算的情况下，请给出能够组成的设备的最大可靠性

输入描述

  • S N // S总的预算，N元器件的种类

total // 元器件的总数，每种型号的元器件可以有多种;

此后有total行具体器件的数据

type reliability price // type 整数类型，代表元器件的类型编号从 0 ~ N-1; reliabilty 整数类型 ，代表元器件的可靠性; price 整数类型 ，代表元器件的价格

输出描述

  • 符合预算的设备的最大可靠性，如果预算无法买齐 N 种器件，则返回 -1

备注

  • 0 <= S,price <= 10000000 0 <= N <= 100 0 <= type <= N-1 0 <= total <= 100000 0 < reliability <= 100000

用例

用例一：
输入：
500 3
6
0 80 100
0 90 200
1 50 50
1 70 210
2 50 100
2 60 150
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
输出：
60
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
  • 1

说明 预算500，设备需要3种元件组成，方案

类型0的第一个(可靠性80),

类型1的第二个(可靠性70),

类型2的第二个(可靠性60),

可以使设备的可靠性最大 60

用例二：
输入：
100 1
1
0 90 200
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
  • 1
  • 2
  • 3
输出：
-1
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

说明 组成设备需要1个元件，但是元件价格大于预算，因此无法组成设备，返回-1

python解法

解题步骤：
数据预处理：

首先通过输入读取并解析开发人员的数据，并将其分类到不同的团队中。
使用 set 来存储开发人员的 rel 值，这有助于我们在后续的二分查找中获得所有不同的 rel 值。
二分查找：

在 rel 值的范围内进行二分查找。每次通过 mid 值（即当前的 rel）来判断是否能在所有团队中找到合适的开发人员，使得他们的总成本不超过预算 s。
二分查找的目标是找到最大的满足条件的 rel 值。
检查一个 rel 是否有效：

对每个团队中的开发人员按照 rel 排序，并选择 rel 大于等于当前值 r 的开发人员。
如果存在这样一个开发人员，并且选择该开发人员后所有团队的总成本不超过 s，则返回 True，否则返回 False

class Dev:
    def __init__(self, rel, prc):
        # 初始化 Dev 类，rel 表示资历，prc 表示成本
        self.rel = rel
        self.prc = prc

# 读取输入：s 是预算，n 是团队数，t 是开发人员数量
s, n = map(int, input().split())
t = int(input())

# 读取每个开发人员的团队类型、资历和成本
data = [list(map(int, input().split())) for _ in range(t)]

# rel 集合用于存储所有开发人员的资历，确保不重复
rel = set()
# groups 用于存储每个团队的开发人员
groups = [[] for _ in range(n)]

# 将开发人员按照团队分组，并记录每个开发人员的资历和成本
for ty, r, p in data:
    groups[ty].append(Dev(r, p))
    rel.add(r)  # 记录所有不同的资历

# 检查给定资历 r 是否有效的函数
def isValid(r):
    total = 0  # 用于记录总成本
    # 遍历每个团队
    for group in groups:
        group.sort(key=lambda dev: dev.rel)  # 按资历排序
        # 查找第一个资历大于等于 r 的开发人员
        pos = next((i for i, dev in enumerate(group) if dev.rel >= r), len(group))
        if pos == len(group):  # 如果没有找到合适的开发人员
            return False
        total += group[pos].prc  # 将该开发人员的成本加到总成本中
    return total <= s  # 如果总成本不超过预算，返回 True

# 二分查找最大的有效资历 r
def getMax():
    # 将所有不同的资历值排序
    rels = sorted(rel)
    lo, hi, result = 0, len(rels) - 1, -1
    
    # 二分查找
    while lo <= hi:
        mid = (lo + hi) // 2  # 计算中间位置
        if isValid(rels[mid]):  # 如果当前资历有效
            result = rels[mid]  # 记录下当前资历值
            lo = mid + 1  # 向右半区查找更大的资历
        else:
            hi = mid - 1  # 向左半区查找更小的资历
    
    return result

# 输出结果
print(getMax())

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

java解法

输入解析：

首先读取预算 budget，组件类型数 types 和总组件数 totalComponents。
然后读取每个组件的类型、可靠性 reliability 和价格 price，将它们存储到对应的 components 列表中，按组件类型分类。
二分查找：

通过二分查找来确定最大的 reliability，范围从 0 到 100000（假设最大的可靠性为 100000，这个值可以根据具体题目调整）。
每次取中间值 mid，判断是否能在预算 budget 内选择满足 reliability >= mid 的组件。如果可以，就尝试更大的 reliability；否则尝试更小的 reliability。
判断是否能够在预算内选择组件：

对于每个组件类型，选择一个可靠性大于等于当前 mid 的最小价格的组件，并将其价格累加。
如果所有类型都有一个符合条件的组件且总价格不超过预算，返回 true，否则返回 false。
输出结果：

二分查找结束后，输出最大的可行 reliability

import java.util.*;

public class Main {
    // 定义一个 Component 类来存储每个组件的可靠性和价格
    static class Component {
        int reliability, price;

        // 构造函数初始化组件的可靠性和价格
        Component(int r, int p) {
            this.reliability = r;
            this.price = p;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 读取预算、组件类型数、组件总数
        int budget = sc.nextInt();
        int types = sc.nextInt();
        int totalComponents = sc.nextInt();

        // 创建一个列表，列表中的每个元素是一个存储组件的列表
        List<List<Component>> components = new ArrayList<>(types);
        for (int i = 0; i < types; i++) {
            components.add(new ArrayList<>());
        }

        // 读取每个组件的数据，分类存储到对应类型的列表中
        for (int i = 0; i < totalComponents; i++) {
            int type = sc.nextInt();
            int reliability = sc.nextInt();
            int price = sc.nextInt();
            components.get(type).add(new Component(reliability, price));
        }

        // 输出最大的可靠性值，满足预算约束
        System.out.println(findMaxReliability(components, budget));
    }

    // 二分查找最大的可靠性
    private static int findMaxReliability(List<List<Component>> components, int budget) {
        int low = 0, high = 100000, bestReliability = -1;

        // 在 [low, high] 范围内进行二分查找
        while (low <= high) {
            int mid = low + (high - low) / 2;  // 计算中间值

            // 判断是否能选择可靠性大于等于 mid 的组件，且总成本不超过预算
            if (canAfford(components, mid, budget)) {
                bestReliability = mid;  // 更新最佳可靠性
                low = mid + 1;  // 尝试更大的可靠性
            } else {
                high = mid - 1;  // 尝试更小的可靠性
            }
        }

        // 返回最大可行的可靠性
        return bestReliability;
    }

    // 判断能否在预算内选择可靠性大于等于 targetReliability 的组件
    private static boolean canAfford(List<List<Component>> components, int targetReliability, int budget) {
        int cost = 0;

        // 遍历每种组件类型
        for (List<Component> typeList : components) {
            int minPrice = Integer.MAX_VALUE;  // 记录该类型组件中可靠性大于等于 targetReliability 的最小价格

            // 查找该类型中可靠性大于等于 targetReliability 的最小价格
            for (Component comp : typeList) {
                if (comp.reliability >= targetReliability) {
                    minPrice = Math.min(minPrice, comp.price);
                }
            }

            // 如果该类型没有符合条件的组件，则返回 false
            if (minPrice == Integer.MAX_VALUE) return false;

            cost += minPrice;  // 累加选中的组件价格
        }

        // 如果总成本不超过预算，则返回 true
        return cost <= budget;
    }
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

C++解法

更新中
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

C解法

更新中
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

JS解法

解题思路：

输入解析：

我们首先读取预算 s，设备类型的数量 n 和设备的总数 total。
然后将每个设备按其类型分组，同时记录每个设备的可靠性和价格。
二分查找最大可靠性：

由于设备的可靠性范围较大，我们使用二分查找来寻找最大可靠性 r，使得对于这个 r，选出的所有设备的总价格不超过预算。
对每个设备类型，我们选择第一个可靠性大于等于 r 的设备，并累加它们的价格，直到总价格不超过预算。
检查某个可靠性值是否可行：

对于每个设备类型，我们按可靠性排序，使用二分查找来选择可靠性大于等于目标值的设备，计算其价格并检查总和是否在预算之内。
二分查找的辅助函数：

使用二分查找来查找某个可靠性大于等于目标值的设备，确保搜索效率

const rl = require("readline");

// 设备类，包含可靠性和价格属性
class Device {
    constructor(rel, prc) {
        this.rel = rel;  // 可靠性
        this.prc = prc;  // 价格
    }
}

// 主函数
async function run() {
    // 创建接口读取输入
    const r = rl.createInterface({ input: process.stdin });
    const iter = r[Symbol.asyncIterator]();
    const read = async () => (await iter.next()).value;

    // 读取预算和设备类型数量
    const [s, n] = (await read()).split(" ").map(Number);

    // reliabilities 集合存储所有不同的可靠性值
    const reliabilities = new Set();
    // kinds 数组存储每种类型的设备
    const kinds = Array.from({ length: n }, () => []);
    // 读取设备的总数
    const total = parseInt(await read());

    // 读取每个设备的信息
    for (let i = 0; i < total; i++) {
        const [type, reliability, price] = (await read()).split(" ").map(Number);
        reliabilities.add(reliability);  // 记录设备的可靠性
        kinds[type].push(new Device(reliability, price));  // 将设备添加到对应类型的数组中
    }

    // 调用 getResult 函数获取最大可靠性，并输出结果
    console.log(getResult(s, kinds, Array.from(reliabilities).sort((a, b) => a - b)));

    r.close();  // 关闭输入接口
}

// 计算最大可靠性
function getResult(s, kinds, reliabilities) {
    // 对每种类型的设备按可靠性排序
    for (let kind of kinds) {
        kind.sort((a, b) => a.rel - b.rel);
    }

    let ans = -1;
    let low = 0;
    let high = reliabilities.length - 1;

    // 使用二分查找在可靠性范围内寻找最优解
    while (low <= high) {
        const mid = (low + high) >> 1;
        if (check(kinds, reliabilities[mid], s)) {
            ans = reliabilities[mid];  // 如果当前可靠性可以满足条件，更新答案
            low = mid + 1;  // 尝试更大的可靠性
        } else {
            high = mid - 1;  // 尝试更小的可靠性
        }
    }

    return ans;
}

// 检查在给定的最大可靠性下，是否可以选择设备满足预算
function check(kinds, maxReliability, s) {
    let sum = 0;
    for (let kind of kinds) {
        // 使用二分查找选择符合条件的设备
        let idx = binarySearch(kind, maxReliability);
        if (idx < 0) idx = -idx - 1;  // 如果没有直接找到，则返回插入位置
        if (idx === kind.length) return false;  // 如果没有设备符合条件，返回 false
        sum += kind[idx].prc;  // 累加该设备的价格
    }
    return sum <= s;  // 如果总价格不超过预算，返回 true
}

// 二分查找，返回可靠性大于等于 target 的设备的索引
function binarySearch(kind, target) {
    let low = 0;
    let high = kind.length - 1;

    // 二分查找
    while (low <= high) {
        const mid = (low + high) >> 1;
        if (kind[mid].rel > target) {
            high = mid - 1;
        } else if (kind[mid].rel < target) {
            low = mid + 1;
        } else {
            return mid;  // 如果找到目标值，直接返回
        }
    }

    return -low - 1;  // 返回插入位置
}

// 执行主程序
run();

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏

注：本文转载自blog.csdn.net的CodeClimb的文章"https://blog.csdn.net/CodeClimb/article/details/145065667"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！