#P3208. 组装最大可靠性设备(200分)
-
1000ms
Tried: 93
Accepted: 22
Difficulty: 6
所属公司 :
华为od
组装最大可靠性设备(200分)
题面描述
一个设备由 N 种类型元器件组成(每种类型元器件只需要一个,类型 type 编号从 0 ~ N−1)。每个元器件均有可靠性属性 reliability,可靠性越高的器件其价格 price 越贵。设备的可靠性由组成设备的所有器件中可靠性最低的器件决定。
给定预算 S,购买 N 种元器件(每种类型元器件都需要购买一个),在不超过预算的情况下,请给出能够组成的设备的最大可靠性。
如果预算无法买齐 N 种器件,则返回 −1。
思路
该问题要求在预算限制下,选择每种类型的一个元器件,使得设备的可靠性最大化。设备的可靠性由所有选定元器件中最低的可靠性决定。因此,我们需要在满足预算的情况下,尽可能选择高可靠性的元器件。
可以采用二分查找结合贪心策略的方法:
- 收集所有可能的可靠性值:将所有元器件的可靠性值去重后排序,作为二分查找的候选值。
- 二分查找:在可靠性值的范围内,通过二分查找确定最大的可行可靠性值。
- 对于每一个中间可靠性值,检查是否存在一种选择方案,使得每种类型都有一个可靠性不低于该值的元器件,且这些元器件的总价格不超过预算 S。
- 如果存在,则尝试更高的可靠性值;否则,降低候选可靠性值。
- 最终结果:找到最大的可行可靠性值。如果没有可行解,则返回 −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