视频流带宽分配(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选择720P，cam02选择VGA，cam03 选择 VGA, 总带宽2+1+1 = 4

题解

思路：贪心

1. 题目要求接入摄像头尽可能多，总带宽尽可能少，为了在w带宽限制内选择更多摄像头和总带宽少，只需要考虑每种摄像头最低带宽配置，然后尽可能选择带宽少的摄像头类型。
2. 遍历输入配置，提取每中摄像头的最小带宽，使用数组v进行存储。
3. 将数组v进行升序排序
4. 使用count记录选取数量，ansW记录所需带宽，贪心从前往后进行摄像头进行选择，如果当前ansW + v[i] < w即进行选择。

C++

#include<bits/stdc++.h>#include<cctype>#include<vector>usingnamespacestd;vector<string>split(conststring&str,conststring&delimiter){vector<string>result;size_t start=0;size_t end=str.find(delimiter);while(end!=string::npos){result.push_back(str.substr(start,end-start));start=end+delimiter.length();end=str.find(delimiter,start);}// 添加最后一个部分result.push_back(str.substr(start));returnresult;}vector<int>solve(intn,intw,vector<string>&profile){vector<int>v(n);for(inti=0;i<n;i++){vector<string>tmp=split(profile[i]," ");// 只考虑当前摄像头最小带宽配置intminValue=INT_MAX;for(intj=2;j<tmp.size();j+=2){intcurVal=stoi(tmp[j]);minValue=min(minValue,curVal);}v[i]=minValue;}// 升序排序sort(v.begin(),v.end());intcount=0;intansW=0;// 贪心选择带宽下的for(inti=0;i<n;i++){// 无法选择更多摄像头，直接结束if(ansW+v[i]>w){break;}count++;ansW+=v[i];}return{count,ansW};}intmain(){intn,w;cin>>n>>w;cin.ignore();vector<string>profile;string input;for(inti=0;i<n;i++){getline(cin,input);profile.push_back(input);}vector<int>ans=solve(n,w,profile);cout<<ans[0]<<","<<ans[1];return0;}

Java

importjava.util.*;publicclassMain{staticint[]solve(intn,intw,String[]profile){int[]v=newint[n];for(inti=0;i<n;i++){String[]tmp=profile[i].trim().split("\\s+");// 只考虑当前摄像头最小带宽配置intminValue=Integer.MAX_VALUE;for(intj=2;j<tmp.length;j+=2){intcurVal=Integer.parseInt(tmp[j]);minValue=Math.min(minValue,curVal);}v[i]=minValue;}// 升序排序Arrays.sort(v);intcount=0;intansW=0;// 贪心选择带宽下的摄像头for(inti=0;i<n;i++){// 无法选择更多摄像头，直接结束if(ansW+v[i]>w){break;}count++;ansW+=v[i];}returnnewint[]{count,ansW};}publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intn=sc.nextInt();intw=sc.nextInt();sc.nextLine();String[]profile=newString[n];for(inti=0;i<n;i++){profile[i]=sc.nextLine();}int[]ans=solve(n,w,profile);System.out.println(ans[0]+","+ans[1]);sc.close();}}

Python

defsolve(n,w,profile):v=[0]*nforiinrange(n):tmp=profile[i].split()# 只考虑当前摄像头最小带宽配置minValue=float('inf')forjinrange(2,len(tmp),2):curVal=int(tmp[j])minValue=min(minValue,curVal)v[i]=minValue# 升序排序v.sort()count=0ansW=0# 贪心选择带宽下的摄像头foriinrange(n):# 无法选择更多摄像头，直接结束ifansW+v[i]>w:breakcount+=1ansW+=v[i]return[count,ansW]if__name__=="__main__":n,w=map(int,input().split())profile=[]for_inrange(n):profile.append(input())ans=solve(n,w,profile)print(f"{ans[0]},{ans[1]}")

JavaScript

constreadline=require('readline');constrl=readline.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);letprofile=input.slice(1,n+1);functionsolve(n,w,profile){letv=newArray(n);for(leti=0;i<n;i++){lettmp=profile[i].trim().split(/\s+/);// 只考虑当前摄像头最小带宽配置letminValue=Infinity;for(letj=2;j<tmp.length;j+=2){letcurVal=Number(tmp[j]);minValue=Math.min(minValue,curVal);}v[i]=minValue;}// 升序排序v.sort((a,b)=>a-b);letcount=0;letansW=0;// 贪心选择带宽下的摄像头for(leti=0;i<n;i++){// 无法选择更多摄像头，直接结束if(ansW+v[i]>w){break;}count++;ansW+=v[i];}return[count,ansW];}letans=solve(n,w,profile);console.log(ans[0]+","+ans[1]);});

Go

packagemainimport("bufio""fmt""os""sort""strconv""strings")funcsolve(n,wint,profile[]string)[]int{v:=make([]int,n)fori:=0;i<n;i++{tmp:=strings.Fields(profile[i])// 只考虑当前摄像头最小带宽配置minValue:=int(^uint(0)>>1)forj:=2;j<len(tmp);j+=2{curVal,_:=strconv.Atoi(tmp[j])ifcurVal<minValue{minValue=curVal}}v[i]=minValue}// 升序排序sort.Ints(v)count:=0ansW:=0// 贪心选择带宽下的摄像头fori:=0;i<n;i++{// 无法选择更多摄像头，直接结束ifansW+v[i]>w{break}count++ansW+=v[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;i<n;i++{line,_:=in.ReadString('\n')profile[i]=line}ans:=solve(n,w,profile)fmt.Printf("%d,%d\n",ans[0],ans[1])}

C语言

#include<stdio.h>#include<stdlib.h>#include<string.h>#include<limits.h>intcmp(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(inti=0;i<n;i++){char*token=strtok(profile[i]," \t\r\n");intidx=0;intminValue=INT_MAX;while(token!=NULL){// 只考虑当前摄像头最小带宽配置if(idx>=2&&idx%2==0){intcurVal=atoi(token);if(curVal<minValue){minValue=curVal;}}idx++;token=strtok(NULL," \t\r\n");}v[i]=minValue;}// 升序排序qsort(v,n,sizeof(int),cmp);*count=0;*ansW=0;// 贪心选择带宽下的摄像头for(inti=0;i<n;i++){// 无法选择更多摄像头，直接结束if(*ansW+v[i]>w){break;}(*count)++;*ansW+=v[i];}free(v);}intmain(){intn,w;scanf("%d %d",&n,&w);getchar();charprofile[1200][10000];for(inti=0;i<n;i++){fgets(profile[i],sizeof(profile[i]),stdin);}intcount=0;intansW=0;solve(n,w,profile,&count,&ansW);printf("%d,%d\n",count,ansW);return0;}