目录题目思路Code题目在大语言模型推理服务中有多个不同大小的模型版本可供选择。每个模型版本有不同的准确率和推理延迟。给定查询次数 N 和总时间预算 T为每个查询选择一个模型版本使得在不超过时间预算的前提下总准确率最大。输入描述- 查询次数 N- 总时间预算 T- 模型准确率 accuracy[i]- 模型延迟 latency[i]输出描述最大总准确率补充说明- 同一个模型可以被多次选择- 0 查询数量 N 10- 0 总时间预算 T 100- 0 准确率 accuracy[i] 100表示多个百分点- 0 延迟 latency[i] 20- 0 模型版本数量 10- 可以考虑采用递归方法完成- 必须查询 N 次样例1输入2480,90,951,2,3输出180说明最优选择为选取两个准确率为 90 的模型总耗时为 4总准确率为 180。样例2输入2280,90,952,2,3输出0思路二维动态规划状态设计dp[i][t] 表示恰好完成 i 次查询并且总延迟恰好为 t 时能够得到的最大总准确率。如果这种状态无法达到就记为 -1。初始化还没做任何查询时dp[0][0] 0表示做了 0 次查询耗时 0总准确率自然也是 0。其他状态一开始都设为 -1表示不可达。状态转移如果当前已经知道dp[i-1][usedTime]说明前 i-1 次查询已经完成总耗时是 usedTime当前总准确率是这个值。那么第 i 次查询我们可以再枚举任意一个模型这个模型准确率是 acc延迟是 cost如果usedTime cost T那么就可以转移到dp[i][usedTime cost]并更新为dp[i][usedTime cost] max(dp[i][usedTime cost], dp[i-1][usedTime] acc)意思是第 i 次查询选这个模型后新的总耗时增加 cost新的总准确率增加 acc。因为每一步都可以重复枚举所有模型所以天然支持“同一个模型可重复选择”。Codeimport java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; public class Solution { private static int[] parseNumbers(String line) { // 兼容逗号分隔和空白分隔两种输入格式。 String[] parts line.trim().split([,\\s]); int[] nums new int[parts.length]; for (int i 0; i parts.length; i) { nums[i] Integer.parseInt(parts[i]); } return nums; } public static void main(String[] args) throws Exception { BufferedReader reader new BufferedReader(new InputStreamReader(System.in)); ListString lines new ArrayList(); String line; while ((line reader.readLine()) ! null) { // 过滤空行避免因为输入中存在空白行导致解析出错。 line line.trim(); if (!line.isEmpty()) { lines.add(line); } } if (lines.size() 4) { System.out.println(0); return; } int n Integer.parseInt(lines.get(0)); int limit Integer.parseInt(lines.get(1)); int[] accuracy parseNumbers(lines.get(2)); int[] latency parseNumbers(lines.get(3)); int modelCount Math.min(accuracy.length, latency.length); if (n 0 || limit 0 || modelCount 0) { System.out.println(0); return; } int[][] dp new int[n 1][limit 1]; for (int i 0; i n; i) { for (int t 0; t limit; t) { // -1 表示当前状态不可达。 dp[i][t] -1; } } dp[0][0] 0; // dp[i][t] 表示恰好完成 i 次查询、总耗时为 t 时的最大准确率。 for (int i 1; i n; i) { for (int usedTime 0; usedTime limit; usedTime) { if (dp[i - 1][usedTime] 0) { continue; } for (int j 0; j modelCount; j) { // 第 i 次查询选择第 j 个模型尝试转移到新状态。 int nextTime usedTime latency[j]; if (nextTime limit) { dp[i][nextTime] Math.max(dp[i][nextTime], dp[i - 1][usedTime] accuracy[j]); } } } } int answer 0; for (int t 0; t limit; t) { // 总耗时只要求不超过 limit所以枚举最后一层所有合法时间。 answer Math.max(answer, dp[n][t]); } System.out.println(answer); } }Gopackage main import ( bufio fmt os strconv strings ) func parseNumbers(line string) []int { // 兼容逗号分隔和空白分隔两种输入格式。 line strings.ReplaceAll(line, ,, ) parts : strings.Fields(line) nums : make([]int, 0, len(parts)) for _, part : range parts { value, _ : strconv.Atoi(part) nums append(nums, value) } return nums } func main() { scanner : bufio.NewScanner(os.Stdin) lines : make([]string, 0, 4) for scanner.Scan() { // 过滤空行避免输入格式中的空白行影响解析。 line : strings.TrimSpace(scanner.Text()) if line ! { lines append(lines, line) } } if len(lines) 4 { fmt.Println(0) return } n, _ : strconv.Atoi(lines[0]) limit, _ : strconv.Atoi(lines[1]) accuracy : parseNumbers(lines[2]) latency : parseNumbers(lines[3]) modelCount : len(accuracy) if len(latency) modelCount { modelCount len(latency) } if n 0 || limit 0 || modelCount 0 { fmt.Println(0) return } // dp[i][t] 表示恰好完成 i 次查询、总耗时为 t 时的最大准确率。 // 不可达状态记为 -1。 dp : make([][]int, n1) for i : 0; i n; i { dp[i] make([]int, limit1) for t : 0; t limit; t { dp[i][t] -1 } } dp[0][0] 0 for i : 1; i n; i { for usedTime : 0; usedTime limit; usedTime { if dp[i-1][usedTime] 0 { continue } for j : 0; j modelCount; j { // 第 i 次查询选择第 j 个模型更新新的耗时状态。 nextTime : usedTime latency[j] if nextTime limit { value : dp[i-1][usedTime] accuracy[j] if value dp[i][nextTime] { dp[i][nextTime] value } } } } } answer : 0 for t : 0; t limit; t { // 最终只要求总耗时不超过 limit因此枚举最后一层即可。 if dp[n][t] answer { answer dp[n][t] } } fmt.Println(answer) }C#include stdio.h #include stdlib.h #include string.h #define MAX_LINE 1024 int parse_numbers(char *line, int nums[]) { int count 0; char *token; // 先把逗号替换成空格统一交给 strtok 解析。 for (int i 0; line[i] ! \0; i) { if (line[i] ,) { line[i] ; } } token strtok(line, \t\r\n); while (token ! NULL) { nums[count] atoi(token); token strtok(NULL, \t\r\n); } return count; } int main() { char line[MAX_LINE]; char lines[4][MAX_LINE]; int line_count 0; while (fgets(line, sizeof(line), stdin) ! NULL) { int all_blank 1; // 跳过空白行避免样例中的空行影响输入。 for (int i 0; line[i] ! \0; i) { if (line[i] ! line[i] ! \t line[i] ! \r line[i] ! \n) { all_blank 0; break; } } if (!all_blank line_count 4) { strcpy(lines[line_count], line); } } if (line_count 4) { printf(0\n); return 0; } int n atoi(lines[0]); int limit atoi(lines[1]); int accuracy[128]; int latency[128]; int acc_count parse_numbers(lines[2], accuracy); int lat_count parse_numbers(lines[3], latency); int model_count acc_count lat_count ? acc_count : lat_count; if (n 0 || limit 0 || model_count 0) { printf(0\n); return 0; } // dp[i][t] 表示恰好完成 i 次查询、总耗时为 t 时的最大准确率。 // -1 表示该状态不可达。 int dp[16][128]; for (int i 0; i n; i) { for (int t 0; t limit; t) { dp[i][t] -1; } } dp[0][0] 0; // dp[i][t] 表示恰好完成 i 次查询、总耗时为 t 时的最大准确率。 for (int i 1; i n; i) { for (int used_time 0; used_time limit; used_time) { if (dp[i - 1][used_time] 0) { continue; } for (int j 0; j model_count; j) { // 第 i 次查询选择当前模型尝试更新新状态。 int next_time used_time latency[j]; if (next_time limit) { int value dp[i - 1][used_time] accuracy[j]; if (value dp[i][next_time]) { dp[i][next_time] value; } } } } } int answer 0; for (int t 0; t limit; t) { // 总耗时不超过 limit 的所有状态里取最大值。 if (dp[n][t] answer) { answer dp[n][t]; } } printf(%d\n, answer); return 0; }【华为od机试真题PythonJSJavaGo合集】【超值优惠】Py/JS/Java/Go合集【华为od机试真题Python】Python真题题库【华为od机试真题JavaScript】JavaScript真题题库【华为od机试真题JavaGo】JavaGo真题题库【华为od机试真题C】C真题题库【华为od机试真题C语言】C语言真题题库【华为od面试手撕代码题库】面试手撕代码题库【华为od机试面试交流群】【文章底部有二维码链接可扫码加交流群】华为OD机试:二本院校有机会吗?有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。
