视频流带宽分配(Java /Py/C/C/Js/Go)题解华为OD机试真题 新系统 华为OD上机考试真题新系统 10月25号 200分题型华为OD机试新系统真题目录点击查看: 华为OD机试新系统真题题库目录机考题库 算法考点详解题目内容视频监控系统中每个摄像头可通过Profile配置多种视频流规则不同的Profile对应不同的带宽占用画质越好占用带宽越大。监控中心须在有限的带宽W内接入摄像头视频流现给定n个摄像头以及可选配置请为每个摄像头选择一种配置或者不接入该摄像头满足总带宽不超W接入摄像头尽可能多接入摄像头尽可能多的情况下总带宽尽可能小每个摄像头最多选一个Profile不选择不占用带宽。输入描述摄像头数量n:整型格式带宽上限值w:整型摄像头配置列表每行成员格式为标识 配置名 带宽 配置名 带宽....输出描述输出最大摄像头数量,最小总带宽无法选中任何配置输出0,0样例1输入3 6 cam01 1080P 6 720P 2 cam02 720P 3 VGA 1 cam03 VGA 1输出3,4说明三个摄像头均可选中cam01选择720Pcam02选择VGAcam03 选择 VGA, 总带宽211 4题解思路贪心题目要求接入摄像头尽可能多总带宽尽可能少为了在w带宽限制内选择更多摄像头和总带宽少只需要考虑每种摄像头最低带宽配置然后尽可能选择带宽少的摄像头类型。遍历输入配置提取每中摄像头的最小带宽使用数组v进行存储。将数组v进行升序排序使用count记录选取数量ansW记录所需带宽贪心从前往后进行摄像头进行选择如果当前ansW v[i] w即进行选择。C#includebits/stdc.h#includecctype#includevectorusingnamespacestd;vectorstringsplit(conststringstr,conststringdelimiter){vectorstringresult;size_t start0;size_t endstr.find(delimiter);while(end!string::npos){result.push_back(str.substr(start,end-start));startenddelimiter.length();endstr.find(delimiter,start);}// 添加最后一个部分result.push_back(str.substr(start));returnresult;}vectorintsolve(intn,intw,vectorstringprofile){vectorintv(n);for(inti0;in;i){vectorstringtmpsplit(profile[i], );// 只考虑当前摄像头最小带宽配置intminValueINT_MAX;for(intj2;jtmp.size();j2){intcurValstoi(tmp[j]);minValuemin(minValue,curVal);}v[i]minValue;}// 升序排序sort(v.begin(),v.end());intcount0;intansW0;// 贪心选择带宽下的for(inti0;in;i){// 无法选择更多摄像头直接结束if(ansWv[i]w){break;}count;ansWv[i];}return{count,ansW};}intmain(){intn,w;cinnw;cin.ignore();vectorstringprofile;string input;for(inti0;in;i){getline(cin,input);profile.push_back(input);}vectorintanssolve(n,w,profile);coutans[0],ans[1];return0;}Javaimportjava.util.*;publicclassMain{staticint[]solve(intn,intw,String[]profile){int[]vnewint[n];for(inti0;in;i){String[]tmpprofile[i].trim().split(\\s);// 只考虑当前摄像头最小带宽配置intminValueInteger.MAX_VALUE;for(intj2;jtmp.length;j2){intcurValInteger.parseInt(tmp[j]);minValueMath.min(minValue,curVal);}v[i]minValue;}// 升序排序Arrays.sort(v);intcount0;intansW0;// 贪心选择带宽下的摄像头for(inti0;in;i){// 无法选择更多摄像头直接结束if(ansWv[i]w){break;}count;ansWv[i];}returnnewint[]{count,ansW};}publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);intnsc.nextInt();intwsc.nextInt();sc.nextLine();String[]profilenewString[n];for(inti0;in;i){profile[i]sc.nextLine();}int[]anssolve(n,w,profile);System.out.println(ans[0],ans[1]);sc.close();}}Pythondefsolve(n,w,profile):v[0]*nforiinrange(n):tmpprofile[i].split()# 只考虑当前摄像头最小带宽配置minValuefloat(inf)forjinrange(2,len(tmp),2):curValint(tmp[j])minValuemin(minValue,curVal)v[i]minValue# 升序排序v.sort()count0ansW0# 贪心选择带宽下的摄像头foriinrange(n):# 无法选择更多摄像头直接结束ifansWv[i]w:breakcount1ansWv[i]return[count,ansW]if__name____main__:n,wmap(int,input().split())profile[]for_inrange(n):profile.append(input())anssolve(n,w,profile)print(f{ans[0]},{ans[1]})JavaScriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});letinput[];rl.on(line,line{input.push(line);});rl.on(close,(){let[n,w]input[0].trim().split(/\s/).map(Number);letprofileinput.slice(1,n1);functionsolve(n,w,profile){letvnewArray(n);for(leti0;in;i){lettmpprofile[i].trim().split(/\s/);// 只考虑当前摄像头最小带宽配置letminValueInfinity;for(letj2;jtmp.length;j2){letcurValNumber(tmp[j]);minValueMath.min(minValue,curVal);}v[i]minValue;}// 升序排序v.sort((a,b)a-b);letcount0;letansW0;// 贪心选择带宽下的摄像头for(leti0;in;i){// 无法选择更多摄像头直接结束if(ansWv[i]w){break;}count;ansWv[i];}return[count,ansW];}letanssolve(n,w,profile);console.log(ans[0],ans[1]);});Gopackagemainimport(bufiofmtossortstrconvstrings)funcsolve(n,wint,profile[]string)[]int{v:make([]int,n)fori:0;in;i{tmp:strings.Fields(profile[i])// 只考虑当前摄像头最小带宽配置minValue:int(^uint(0)1)forj:2;jlen(tmp);j2{curVal,_:strconv.Atoi(tmp[j])ifcurValminValue{minValuecurVal}}v[i]minValue}// 升序排序sort.Ints(v)count:0ansW:0// 贪心选择带宽下的摄像头fori:0;in;i{// 无法选择更多摄像头直接结束ifansWv[i]w{break}countansWv[i]}return[]int{count,ansW}}funcmain(){in:bufio.NewReader(os.Stdin)// 读取第一行line,_:in.ReadString(\n)nums:strings.Fields(line)n,_:strconv.Atoi(nums[0])w,_:strconv.Atoi(nums[1])profile:make([]string,n)// 逐行读取摄像头配置fori:0;in;i{line,_:in.ReadString(\n)profile[i]line}ans:solve(n,w,profile)fmt.Printf(%d,%d\n,ans[0],ans[1])}C语言#includestdio.h#includestdlib.h#includestring.h#includelimits.hintcmp(constvoid*a,constvoid*b){return(*(int*)a*(int*)b)-(*(int*)a*(int*)b);}voidsolve(intn,intw,charprofile[][10000],int*count,int*ansW){int*v(int*)malloc(n*sizeof(int));for(inti0;in;i){char*tokenstrtok(profile[i], \t\r\n);intidx0;intminValueINT_MAX;while(token!NULL){// 只考虑当前摄像头最小带宽配置if(idx2idx%20){intcurValatoi(token);if(curValminValue){minValuecurVal;}}idx;tokenstrtok(NULL, \t\r\n);}v[i]minValue;}// 升序排序qsort(v,n,sizeof(int),cmp);*count0;*ansW0;// 贪心选择带宽下的摄像头for(inti0;in;i){// 无法选择更多摄像头直接结束if(*ansWv[i]w){break;}(*count);*ansWv[i];}free(v);}intmain(){intn,w;scanf(%d %d,n,w);getchar();charprofile[1200][10000];for(inti0;in;i){fgets(profile[i],sizeof(profile[i]),stdin);}intcount0;intansW0;solve(n,w,profile,count,ansW);printf(%d,%d\n,count,ansW);return0;}