网硕互联帮助中心目录
题目
思路
Code
题目
某云计算服务商为客户提供 M 数量 GPU 核数的 GPU 分时租用服务，租用计费规则为:允许客户在每个时间单位按需租用不同的 GPU 核数，每个时间单位每个 GPU 核数的费用为 R。 现有 N 个客户，每个客户有多个不重叠时间段租用一定数量的 GPU 核数的租用需求。对于有租用需求的客户，服务商可选择签约或不签约，若选择签约则需要满足租用需求中的所有时间段所需的 GPU 核数。 为了实现租金最大化收益，服务商需在确保任意时间单位内分配的 GPU 核数总数不超过 M 的基础上，选择与哪些客户签约租用协议。 请输出租金最大化收益下的租金最大值. 输入描述 第一行为 M、N、R的数值，依次用空格隔开，输入格式为 M N R 从第二行开始，每行为一个客户的租用需求，共 N 行。每行的9第一个数字为该客户端的时间段个数timeSegmentNum ，后续为 timeSegmentNum 个时间段及所需的 GPU 核数，时间段个数timeSegmentNum 与时间段之间、多个时间段之间均用空格分割。同一个客户多个时间段不会重叠。同一个客户多个时间段已按起始时间增序排序给出 每个时间段及所需的GPU核数, 格式为 star 起始时间编号:end 结束时间编号:needCores 该时间段所需的 GPU 核数 变量取值范围 1 <= M <= 100000 1 <= N <= 10 1 <= R<= 10 0 <= start <= end <= 109 1<= needCores <= 10000 1 <=timeSegmentNum <= 100 客户的租用需求样例20:0:13:6:10 的含义是共有2个时间段,0:0:1表示在第0个时间单位需要1个GPU核，3:6:10 表示在从 3 到6的时间单位(包含3和6)每个时间单位均需 10 个GPU 核.
输出描述 总租金最大值。 如果任意一个客户的需求都无法满足，则输出 0
示例1： 输入： 10 3 2 2 0:8:5 9:23:10 2 0:8:5 9:18:10 1 0:8:5
输出： 480 说明： 共3个客户。 由于第一个客户和第三个客户在 9:18 时间范围段内总核数为 20 超过了 10，所以无法同时接受最大日租金方案为:接纳第一个客户和第三个客户的需求。 第一个客户共需要的 GPU 核数为9*5+ 15*10 = 195 第三个每户共需要的 GPU 核数为 9*5 = 45 最大日租金值为(195 +45)*2= 480
示例2： 输入： 10 2 1 1 0:3:6 1 3:10:6
输出： 48 说明： 最大 GPU 核数为 10 ，共 2 个客户。 第一个客户和第二个客户在 3 时间点，总核数为 12 超过了 10 ，所以无法同时接受 第一个客户共需要的 GPU 核数为4*6=24 第三个每户共需要的 GPU 核数为8*6=48 为满足最大租金，采纳第二个客户，最大日租金值为 48*1=48
Python
def calculate_max_rent(M, N, R, customers):
"""
计算最大租金收益
:param M: GPU总核数
:param N: 客户数量
:param R: 单位租金
:param customers: 客户需求列表
:return: 最大租金
"""
# 存储所有时间点的GPU使用情况
time_usage = {}
max_rent = [0] # 使用列表存储最大租金，便于在递归中修改
def check_valid(customer_idx):
"""
检查添加某个客户后是否超过GPU限制
:param customer_idx: 客户索引
:return: 是否有效
"""
for segment in customers[customer_idx]:
start, end, cores = segment
for t in range(start, end + 1):
if time_usage.get(t, 0) + cores > M:
return False
return True
def add_customer(customer_idx):
"""
添加客户的GPU使用量
:param customer_idx: 客户索引
"""
rent = 0
for segment in customers[customer_idx]:
start, end, cores = segment
for t in range(start, end + 1):
time_usage[t] = time_usage.get(t, 0) + cores
rent += (end – start + 1) * cores
return rent
def remove_customer(customer_idx):
"""
移除客户的GPU使用量
:param customer_idx: 客户索引
"""
for segment in customers[customer_idx]:
start, end, cores = segment
for t in range(start, end + 1):
time_usage[t] = time_usage.get(t, 0) – cores
def backtrack(idx, current_rent):
"""
回溯函数
:param idx: 当前处理的客户索引
:param current_rent: 当前租金
"""
if idx == N:
max_rent[0] = max(max_rent[0], current_rent)
return
# 不选择当前客户
backtrack(idx + 1, current_rent)
# 尝试选择当前客户
if check_valid(idx):
rent = add_customer(idx)
backtrack(idx + 1, current_rent + rent)
remove_customer(idx)
# 解析输入数据
parsed_customers = []
for customer in customers:
segments = []
num_segments = customer[0]
i = 1
while i < len(customer):
start, end, cores = map(int, customer[i].split(':'))
segments.append((start, end, cores))
i += 1
parsed_customers.append(segments)
# 开始回溯
backtrack(0, 0)
return max_rent[0] * R
def parse_input():
"""
解析输入数据
返回：M, N, R 和客户需求列表
"""
# 读取第一行
M, N, R = map(int, input().split())
# 读取客户需求
customers = []
for _ in range(N):
# 解析每行数据
line = input().split()
num_segments = int(line[0]) # 第一个数字是时间段数量
# 解析该客户的所有时间段
segments = []
for i in range(1, num_segments + 1):
start, end, cores = map(int, line[i].split(':'))
segments.append((start, end, cores))
customers.append(segments)
return M, N, R, customers
def main():
# 解析输入
M, N, R, customers = parse_input()
# 计算最大租金
result = calculate_max_rent(M, N, R, customers)
print(result)
if __name__ == "__main__":
main()
Java
import java.util.*;
public class Main {
static int M, N, R;
static List<List<Segment>> customers;
static Map<Integer, Integer> timeUsage;
static int maxRent;
// 定义时间段类
static class Segment {
int start, end, cores;
Segment(int start, int end, int cores) {
this.start = start;
this.end = end;
this.cores = cores;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取基本参数
M = scanner.nextInt();
N = scanner.nextInt();
R = scanner.nextInt();
scanner.nextLine(); // 消耗换行符
// 初始化数据结构
customers = new ArrayList<>();
timeUsage = new HashMap<>();
maxRent = 0;
// 读取客户需求
for (int i = 0; i < N; i++) {
String[] parts = scanner.nextLine().split(" ");
int numSegments = Integer.parseInt(parts[0]);
List<Segment> customerSegments = new ArrayList<>();
// 解析每个时间段
for (int j = 1; j <= numSegments; j++) {
String[] segmentParts = parts[j].split(":");
int start = Integer.parseInt(segmentParts[0]);
int end = Integer.parseInt(segmentParts[1]);
int cores = Integer.parseInt(segmentParts[2]);
customerSegments.add(new Segment(start, end, cores));
}
customers.add(customerSegments);
}
// 开始回溯计算
backtrack(0, 0);
// 输出结果
System.out.println(maxRent * R);
scanner.close();
}
// 检查是否可以添加客户
static boolean checkValid(int customerIdx) {
for (Segment seg : customers.get(customerIdx)) {
for (int t = seg.start; t <= seg.end; t++) {
if (timeUsage.getOrDefault(t, 0) + seg.cores > M) {
return false;
}
}
}
return true;
}
// 添加客户的GPU使用量并返回租金
static int addCustomer(int customerIdx) {
int rent = 0;
for (Segment seg : customers.get(customerIdx)) {
for (int t = seg.start; t <= seg.end; t++) {
timeUsage.put(t, timeUsage.getOrDefault(t, 0) + seg.cores);
}
rent += (seg.end – seg.start + 1) * seg.cores;
}
return rent;
}
// 移除客户的GPU使用量
static void removeCustomer(int customerIdx) {
for (Segment seg : customers.get(customerIdx)) {
for (int t = seg.start; t <= seg.end; t++) {
timeUsage.put(t, timeUsage.get(t) – seg.cores);
}
}
}
// 回溯函数
static void backtrack(int idx, int currentRent) {
if (idx == N) {
maxRent = Math.max(maxRent, currentRent);
return;
}
// 不选择当前客户
backtrack(idx + 1, currentRent);
// 尝试选择当前客户
if (checkValid(idx)) {
int rent = addCustomer(idx);
backtrack(idx + 1, currentRent + rent);
removeCustomer(idx);
}
}
}
C++
#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
#include <sstream>
using namespace std;
// 定义时间段结构
struct Segment {
int start, end, cores;
Segment(int s, int e, int c) : start(s), end(e), cores(c) {}
};
class GPURental {
private:
int M, N, R;
vector<vector<Segment>> customers;
unordered_map<int, int> timeUsage;
int maxRent;
// 检查是否可以添加客户
bool checkValid(int customerIdx) {
for (const auto& seg : customers[customerIdx]) {
for (int t = seg.start; t <= seg.end; t++) {
if (timeUsage[t] + seg.cores > M) {
return false;
}
}
}
return true;
}
// 添加客户的GPU使用量
int addCustomer(int customerIdx) {
int rent = 0;
for (const auto& seg : customers[customerIdx]) {
for (int t = seg.start; t <= seg.end; t++) {
timeUsage[t] += seg.cores;
}
rent += (seg.end – seg.start + 1) * seg.cores;
}
return rent;
}
// 移除客户的GPU使用量
void removeCustomer(int customerIdx) {
for (const auto& seg : customers[customerIdx]) {
for (int t = seg.start; t <= seg.end; t++) {
timeUsage[t] -= seg.cores;
}
}
}
// 回溯函数
void backtrack(int idx, int currentRent) {
if (idx == N) {
maxRent = max(maxRent, currentRent);
return;
}
// 不选择当前客户
backtrack(idx + 1, currentRent);
// 尝试选择当前客户
if (checkValid(idx)) {
int rent = addCustomer(idx);
backtrack(idx + 1, currentRent + rent);
removeCustomer(idx);
}
}
public:
GPURental() : maxRent(0) {}
// 解析输入并求解
int solve() {
// 读取基本参数
cin >> M >> N >> R;
cin.ignore(); // 忽略换行符
// 读取客户需求
for (int i = 0; i < N; i++) {
string line;
getline(cin, line);
istringstream iss(line);
int numSegments;
iss >> numSegments;
vector<Segment> customerSegments;
string segmentStr;
// 读取每个时间段
for (int j = 0; j < numSegments; j++) {
iss >> segmentStr;
size_t pos1 = segmentStr.find(':');
size_t pos2 = segmentStr.find(':', pos1 + 1);
int start = stoi(segmentStr.substr(0, pos1));
int end = stoi(segmentStr.substr(pos1 + 1, pos2 – pos1 – 1));
int cores = stoi(segmentStr.substr(pos2 + 1));
customerSegments.emplace_back(start, end, cores);
}
customers.push_back(customerSegments);
}
// 开始回溯计算
backtrack(0, 0);
return maxRent * R;
}
};
int main() {
GPURental solver;
cout << solver.solve() << endl;
return 0;
}
JavaScript
const readline = require('readline');
class GPURental {
constructor() {
this.M = 0;
this.N = 0;
this.R = 0;
this.customers = [];
this.timeUsage = new Map();
this.maxRent = 0;
}
// 检查是否可以添加客户
checkValid(customerIdx) {
for (const segment of this.customers[customerIdx]) {
for (let t = segment.start; t <= segment.end; t++) {
if ((this.timeUsage.get(t) || 0) + segment.cores > this.M) {
return false;
}
}
}
return true;
}
// 添加客户的GPU使用量
addCustomer(customerIdx) {
let rent = 0;
for (const segment of this.customers[customerIdx]) {
for (let t = segment.start; t <= segment.end; t++) {
this.timeUsage.set(t, (this.timeUsage.get(t) || 0) + segment.cores);
}
rent += (segment.end – segment.start + 1) * segment.cores;
}
return rent;
}
// 移除客户的GPU使用量
removeCustomer(customerIdx) {
for (const segment of this.customers[customerIdx]) {
for (let t = segment.start; t <= segment.end; t++) {
this.timeUsage.set(t, (this.timeUsage.get(t) || 0) – segment.cores);
}
}
}
// 回溯函数
backtrack(idx, currentRent) {
if (idx === this.N) {
this.maxRent = Math.max(this.maxRent, currentRent);
return;
}
// 不选择当前客户
this.backtrack(idx + 1, currentRent);
// 尝试选择当前客户
if (this.checkValid(idx)) {
const rent = this.addCustomer(idx);
this.backtrack(idx + 1, currentRent + rent);
this.removeCustomer(idx);
}
}
// 解析输入并求解
solve(input) {
const lines = input.trim().split('\\n');
// 解析第一行
[this.M, this.N, this.R] = lines[0].split(' ').map(Number);
// 解析客户需求
for (let i = 1; i <= this.N; i++) {
const parts = lines[i].split(' ');
const numSegments = parseInt(parts[0]);
const segments = [];
// 解析每个时间段
for (let j = 1; j <= numSegments; j++) {
const [start, end, cores] = parts[j].split(':').map(Number);
segments.push({ start, end, cores });
}
this.customers.push(segments);
}
// 开始回溯计算
this.backtrack(0, 0);
return this.maxRent * this.R;
}
}
// 处理输入
let inputLines = [];
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
rl.on('line', (line) => {
inputLines.push(line);
});
rl.on('close', () => {
const solver = new GPURental();
console.log(solver.solve(inputLines.join('\\n')));
});
C语言
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_N 10
#define MAX_SEGMENTS 100
#define MAX_LINE 1024
// 定义时间段结构
struct Segment {
int start;
int end;
int cores;
};
// 定义客户结构
struct Customer {
int numSegments;
struct Segment segments[MAX_SEGMENTS];
};
// 全局变量
int M, N, R;
struct Customer customers[MAX_N];
int* timeUsage = NULL; // 使用动态分配的数组
int maxRent = 0;
int maxTime = 0; // 跟踪最大时间值
// 检查是否可以添加客户
int checkValid(int customerIdx) {
struct Customer* customer = &customers[customerIdx];
for (int i = 0; i < customer->numSegments; i++) {
struct Segment* seg = &customer->segments[i];
for (int t = seg->start; t <= seg->end; t++) {
if (timeUsage[t] + seg->cores > M) {
return 0;
}
}
}
return 1;
}
// 添加客户的GPU使用量
int addCustomer(int customerIdx) {
int rent = 0;
struct Customer* customer = &customers[customerIdx];
for (int i = 0; i < customer->numSegments; i++) {
struct Segment* seg = &customer->segments[i];
for (int t = seg->start; t <= seg->end; t++) {
timeUsage[t] += seg->cores;
}
rent += (seg->end – seg->start + 1) * seg->cores;
}
return rent;
}
// 移除客户的GPU使用量
void removeCustomer(int customerIdx) {
struct Customer* customer = &customers[customerIdx];
for (int i = 0; i < customer->numSegments; i++) {
struct Segment* seg = &customer->segments[i];
for (int t = seg->start; t <= seg->end; t++) {
timeUsage[t] -= seg->cores;
}
}
}
// 回溯函数
void backtrack(int idx, int currentRent) {
if (idx == N) {
if (currentRent > maxRent) {
maxRent = currentRent;
}
return;
}
// 不选择当前客户
backtrack(idx + 1, currentRent);
// 尝试选择当前客户
if (checkValid(idx)) {
int rent = addCustomer(idx);
backtrack(idx + 1, currentRent + rent);
removeCustomer(idx);
}
}
// 解析时间段字符串
void parseSegment(char* str, struct Segment* segment) {
char* start = str;
char* end = strchr(str, ':');
*end = '\\0';
segment->start = atoi(start);
start = end + 1;
end = strchr(start, ':');
*end = '\\0';
segment->end = atoi(start);
start = end + 1;
segment->cores = atoi(start);
// 更新最大时间值
if (segment->end > maxTime) {
maxTime = segment->end;
}
}
int main() {
char line[MAX_LINE];
// 读取基本参数
scanf("%d %d %d\\n", &M, &N, &R);
// 读取客户需求
for (int i = 0; i < N; i++) {
fgets(line, MAX_LINE, stdin);
char* token = strtok(line, " \\n");
customers[i].numSegments = atoi(token);
for (int j = 0; j < customers[i].numSegments; j++) {
token = strtok(NULL, " \\n");
parseSegment(token, &customers[i].segments[j]);
}
}
// 分配时间使用数组
timeUsage = (int*)calloc(maxTime + 1, sizeof(int));
if (timeUsage == NULL) {
printf("Memory allocation failed\\n");
return 1;
}
// 开始回溯计算
backtrack(0, 0);
// 输出结果
printf("%d\\n", maxRent * R);
// 释放内存
free(timeUsage);
return 0;
}
【华为od机试真题Python+JS+Java合集】【超值优惠】：Py/JS/Java合集
【华为od机试真题Python】：Python真题题库
【华为od机试真题JavaScript】：JavaScript真题题库
【华为od机试真题Java】：Java真题题库
【华为od机试真题C++】：C++真题题库
【华为od机试真题C语言】：C语言真题题库
【华为od面试手撕代码题库】：面试手撕代码题库
【华为校招&实习机试面试交流群：1048120678】
评论前必须登录！
注册