题面描述

一个设备由 $N$ 种类型元器件组成（每种类型元器件只需要一个，类型 $type$ 编号从 $0$ ~ $N-1$）。每个元器件均有可靠性属性 $reliability$，可靠性越高的器件其价格 $price$ 越贵。设备的可靠性由组成设备的所有器件中可靠性最低的器件决定。

给定预算 $S$，购买 $N$ 种元器件（每种类型元器件都需要购买一个），在不超过预算的情况下，请给出能够组成的设备的最大可靠性。

如果预算无法买齐 $N$ 种器件，则返回 $-1$。

思路

该问题要求在预算限制下，选择每种类型的一个元器件，使得设备的可靠性最大化。设备的可靠性由所有选定元器件中最低的可靠性决定。因此，我们需要在满足预算的情况下，尽可能选择高可靠性的元器件。

可以采用二分查找结合贪心策略的方法：

1. 收集所有可能的可靠性值：将所有元器件的可靠性值去重后排序，作为二分查找的候选值。
2. 二分查找：在可靠性值的范围内，通过二分查找确定最大的可行可靠性值。
   • 对于每一个中间可靠性值，检查是否存在一种选择方案，使得每种类型都有一个可靠性不低于该值的元器件，且这些元器件的总价格不超过预算 $S$。
   • 如果存在，则尝试更高的可靠性值；否则，降低候选可靠性值。
3. 最终结果：找到最大的可行可靠性值。如果没有可行解，则返回 $-1$。

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

class Device {
public:
    int reliability;
    int price;
    
    Device(int r, int p) : reliability(r), price(p) {}
};

int s, n;  // 总预算 s, 器件种类数 n
vector<vector<Device>> kinds;  // 各种类的设备集合
set<int> reliabilities;  // 收集器件的可靠性

// 二分查找
int binarySearch(vector<Device>& kind, int target) {
    int low = 0, high = kind.size() - 1;

    while (low <= high) {
        int mid = (low + high) / 2;
        Device device = kind[mid];

        if (device.reliability > target) {
            high = mid - 1;
        } else if (device.reliability < target) {
            low = mid + 1;
        } else {
            return mid;
        }
    }

    return -low - 1;
}

// 检查函数
bool check(int maxReliability) {
    int sumPrice = 0;

    for (auto& kind : kinds) {
        int idx = binarySearch(kind, maxReliability);
        
        if (idx < 0) {
            idx = -idx - 1;
        }

        if (idx == kind.size()) {
            return false;
        }

        sumPrice += kind[idx].price;
    }

    return sumPrice <= s;
}

// 获取结果
int getResult() {
    int ans = -1;

    for (auto& kind : kinds) {
        sort(kind.begin(), kind.end(), [](const Device& a, const Device& b) {
            return a.reliability == b.reliability ? a.price < b.price : a.reliability < b.reliability;
        });
    }

    vector<int> maybe(reliabilities.begin(), reliabilities.end());
    sort(maybe.begin(), maybe.end());

    int low = 0, high = maybe.size() - 1;
    while (low <= high) {
        int mid = (low + high) / 2;

        if (check(maybe[mid])) {
            ans = maybe[mid];
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return ans;
}

int main() {
    cin >> s >> n;  // 输入总预算和器件种类数
    int total;
    cin >> total;  // 输入器件的数量
    kinds.resize(n);  // 初始化种类集合

    for (int i = 0; i < total; ++i) {
        int ty, reliability, price;
        cin >> ty >> reliability >> price;
        kinds[ty].emplace_back(reliability, price);
        reliabilities.insert(reliability);
    }

    cout << getResult() << endl;  // 输出结果
    return 0;
}

java

import java.util.*;

public class Main {
    static class Device {
        int reliability;
        int price;

        Device(int r, int p) {
            this.reliability = r;
            this.price = p;
        }
    }

    static int s, n;  // 总预算 s, 器件种类数 n
    static List<List<Device>> kinds = new ArrayList<>();  // 各种类的设备集合
    static Set<Integer> reliabilities = new HashSet<>();  // 收集器件的可靠性

    // 二分查找
    static int binarySearch(List<Device> kind, int target) {
        int low = 0, high = kind.size() - 1;

        while (low <= high) {
            int mid = (low + high) / 2;
            Device device = kind.get(mid);

            if (device.reliability > target) {
                high = mid - 1;
            } else if (device.reliability < target) {
                low = mid + 1;
            } else {
                return mid;
            }
        }

        return -low - 1;
    }

    // 检查函数
    static boolean check(int maxReliability) {
        int sumPrice = 0;

        for (List<Device> kind : kinds) {
            int idx = binarySearch(kind, maxReliability);

            if (idx < 0) {
                idx = -idx - 1;
            }

            if (idx == kind.size()) {
                return false;
            }

            sumPrice += kind.get(idx).price;
        }

        return sumPrice <= s;
    }

    // 获取结果
    static int getResult() {
        int ans = -1;

        // 对每种类的设备按可靠性升序，价格升序排序
        for (List<Device> kind : kinds) {
            kind.sort((a, b) -> {
                if (a.reliability != b.reliability) {
                    return a.reliability - b.reliability;
                } else {
                    return a.price - b.price;
                }
            });
        }

        // 收集所有可能的可靠性值并排序
        List<Integer> maybe = new ArrayList<>(reliabilities);
        Collections.sort(maybe);

        // 使用二分查找确定最大的可靠性值
        int low = 0, high = maybe.size() - 1;
        while (low <= high) {
            int mid = (low + high) / 2;

            if (check(maybe.get(mid))) {
                ans = maybe.get(mid);
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        s = scanner.nextInt(); // 输入总预算
        n = scanner.nextInt(); // 输入器件种类数
        int total = scanner.nextInt(); // 输入器件的数量

        // 初始化种类集合
        for (int i = 0; i < n; i++) {
            kinds.add(new ArrayList<>());
        }

        // 输入每个器件的信息
        for (int i = 0; i < total; i++) {
            int ty = scanner.nextInt();
            int reliability = scanner.nextInt();
            int price = scanner.nextInt();
            kinds.get(ty).add(new Device(reliability, price));
            reliabilities.add(reliability);
        }

        // 输出结果
        System.out.println(getResult());
    }
}

python

import sys
from bisect import bisect_left

class Device:
    def __init__(self, reliability: int, price: int):
        self.reliability = reliability
        self.price = price

def binary_search(kind, target):
    low, high = 0, len(kind) - 1
    while low <= high:
        mid = (low + high) // 2
        device = kind[mid]
        if device.reliability > target:
            high = mid - 1
        elif device.reliability < target:
            low = mid + 1
        else:
            return mid
    return -low - 1

def check(kinds, max_reliability, s):
    sum_price = 0
    for kind in kinds:
        idx = binary_search(kind, max_reliability)
        if idx < 0:
            idx = -idx - 1
        if idx == len(kind):
            return False
        sum_price += kind[idx].price
    return sum_price <= s

def get_result(kinds, reliabilities, s):
    # 对每种类的设备按可靠性升序，价格升序排序
    for kind in kinds:
        kind.sort(key=lambda d: (d.reliability, d.price))
    
    # 收集所有可能的可靠性值并排序
    maybe = sorted(reliabilities)
    
    # 使用二分查找确定最大的可靠性值
    low, high = 0, len(maybe) - 1
    ans = -1
    while low <= high:
        mid = (low + high) // 2
        if check(kinds, maybe[mid], s):
            ans = maybe[mid]
            low = mid + 1
        else:
            high = mid - 1
    return ans

def main():
    input = sys.stdin.read().split()
    ptr = 0
    s = int(input[ptr]); ptr += 1  # 输入总预算
    n = int(input[ptr]); ptr += 1  # 输入器件种类数
    total = int(input[ptr]); ptr += 1  # 输入器件的数量
    kinds = [[] for _ in range(n)]
    reliabilities = set()
    for _ in range(total):
        ty = int(input[ptr]); ptr += 1
        reliability = int(input[ptr]); ptr += 1
        price = int(input[ptr]); ptr += 1
        kinds[ty].append(Device(reliability, price))
        reliabilities.add(reliability)
    
    result = get_result(kinds, reliabilities, s)
    print(result)

if __name__ == "__main__":
    main()

题目内容

一个设备由 $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$

样例1

输入

500 3
6
0 80 100
0 90 200
1 50 50
1 70 210
2 50 100
2 60 150

输出

60

说明

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

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

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

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

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

样例2

输入

100 1
1
0 90 200

输出

-1

说明

组成设备需要1个元件，但是元件价格大于预算，

因此无法组成设备，返回-1