流量均衡控制华为笔试真题 8月19号 非AI方向第三题 300分题型题目内容某厂商生产的交换机需要对用户的信息进行处理按照信息的类别划分优先级并为每种流量类型设置权重用于在同优先级的场景下让设备优先处理权重更高的消息。具体分类如下流量类型权重媒体流20信令流15内部管理流量5其他流量0假设某台交换机当前由 2 个端口组成一组共同负责消息的接收与处理。这两个端口需要处理的所有消息的权重构成数组arr。请问是否存在一种消息分发方式使得每个端口处理的消息的权重均值相同即能否将权重数组拆分为两个均值相等的子数组本题只要求判断是否存在这样的分组无需考虑多种分组方式。输入描述输入为一个字符串每个数字代表一条消息的权重。权重的取值只能来自上表即20、15、5、020、15、5、020、15、5、0不存在其他值。各权重之间用空格分隔例如5 5 5 20 15 15 5 5 20 15 15 5 5 20 15 15 15数组大小即消息数量满足1≤n≤1001 \le n \le 1001≤n≤100。输出描述第一行输出0或1。1表示存在一种消息分发方式使得各端口处理的消息权重均值相同0表示不存在这样的分发方式。第二行若第一行输出为1则输出其中一个子数组的元素和若两个子数组的元素和不同则输出较小的那一个。若第一行输出为0则本行无需输出。样例 1输入15 20输出0说明不存在任何划分方式能使两个子数组的均值相同因此输出 0。样例 2输入5 20 15 15 5 5 5 20 5 5 15 15输出1 65说明每个端口处理的消息权重可以取5 5 5 20 15 15此时两个端口处理的消息权重均值一致均为10.833310.833310.8333。样例 3输入15 20 5 20输出1 15说明可以划分为两个组均值均为151515第一个组151515子数组元素和为151515第二个组20 5 2020\ 5\ 2020520子数组元素和为454545题解思路思路:动态规划共有n个元素总权重和为T存在合法两个子数组的平均值相等。必定满足以下条件其中一个子数组个数为cnt, 元素和为sumsum / cnt (T - sum) / (n - cnt)sum * n cnt * T基于1的分析使用动态规划定义dp[cnt][sum]表示是否可以选出 cnt 个元素使它们的和为 sum然后使用01背包算法推导出所有存在的cnt,sum状态情况。然后判断遍历dp数组在dp[cnt][sum]为true的情况看是否满足sum / cnt (T - sum) / (n - cnt)sum * n cnt * T的情况满足输出对应结果即可。C#includebits/stdc.husingnamespacestd;intmain(){ios_base::sync_with_stdio(false);cin.tie(nullptr);vectorintarr;intx;inttotal0;while(cinx){arr.push_back(x/5);totalx/5;}intnarr.size();// 无法形成合法方案if(n2){cout0;return0;}// dp[cnt][sum]是否可以选出 cnt 个元素使元素和为 sumvectorvectorbooldp(n1,vectorbool(total1,false));dp[0][0]true;for(intx:arr){// 0/1 背包必须从大到小枚举for(intcntn;cnt1;cnt--){for(intsumtotal;sumx;sum--){dp[cnt][sum]dp[cnt][sum]|dp[cnt-1][sum-x];}}}for(intcnt1;cntn;cnt){for(intsum0;sumtotal;sum){if(!dp[cnt][sum]){continue;}// 两个子集平均值相同// sum / cnt (total - sum) / (n - cnt) sum * n cnt * totalif(sum*ncnt*total){intotherSumtotal-sum;cout1endl;coutmin(sum,otherSum)*5endl;return0;}}}cout0\n;return0;}javaimportjava.io.*;importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args)throwsException{BufferedReaderbrnewBufferedReader(newInputStreamReader(System.in));StringBuildersbnewStringBuilder();Stringline;while((linebr.readLine())!null){sb.append(line).append( );}String[]inputsb.toString().trim().split(\\s);ListIntegerarrnewArrayList();inttotal0;for(Stringstr:input){intxInteger.parseInt(str);arr.add(x/5);totalx/5;}intnarr.size();// 无法形成合法方案if(n2){System.out.println(0);return;}// dp[cnt][sum]是否可以选出 cnt 个元素使元素和为 sumboolean[][]dpnewboolean[n1][total1];dp[0][0]true;for(intx:arr){// 0/1 背包必须从大到小枚举for(intcntn;cnt1;cnt--){for(intsumtotal;sumx;sum--){dp[cnt][sum]dp[cnt][sum]||dp[cnt-1][sum-x];}}}for(intcnt1;cntn;cnt){for(intsum0;sumtotal;sum){if(!dp[cnt][sum]){continue;}// 两个子集平均值相同// sum / cnt (total - sum) / (n - cnt) sum * n cnt * totalif(sum*ncnt*total){intotherSumtotal-sum;System.out.println(1);System.out.println(Math.min(sum,otherSum)*5);return;}}}System.out.println(0);}}pythonimportsys datasys.stdin.read().split()arr[]total0forvalueindata:xint(value)arr.append(x//5)totalx//5nlen(arr)# 无法形成合法方案ifn2:print(0)sys.exit()# dp[cnt][sum]是否可以选出 cnt 个元素使元素和为 sumdp[[False]*(total1)for_inrange(n1)]dp[0][0]Trueforxinarr:# 0/1 背包必须从大到小枚举forcntinrange(n,0,-1):forsum_valueinrange(total,x-1,-1):dp[cnt][sum_value](dp[cnt][sum_value]ordp[cnt-1][sum_value-x])forcntinrange(1,n):forsum_valueinrange(total1):ifnotdp[cnt][sum_value]:continue# 两个子集平均值相同# sum / cnt (total - sum) / (n - cnt) sum * n cnt * totalifsum_value*ncnt*total:other_sumtotal-sum_valueprint(1)print(min(sum_value,other_sum)*5)sys.exit()print(0)javascriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});constinput[];rl.on(line,line{input.push(line);});rl.on(close,(){constdatainput.join( ).trim().split(/\s/);constarr[];lettotal0;for(constvalueofdata){constxNumber(value);arr.push(Math.floor(x/5));totalMath.floor(x/5);}constnarr.length;// 无法形成合法方案if(n2){console.log(0);return;}// dp[cnt][sum]是否可以选出 cnt 个元素使元素和为 sumconstdpArray.from({length:n1},()newArray(total1).fill(false));dp[0][0]true;for(constxofarr){// 0/1 背包必须从大到小枚举for(letcntn;cnt1;cnt--){for(letsumtotal;sumx;sum--){dp[cnt][sum]dp[cnt][sum]||dp[cnt-1][sum-x];}}}for(letcnt1;cntn;cnt){for(letsum0;sumtotal;sum){if(!dp[cnt][sum]){continue;}// 两个子集平均值相同// sum / cnt (total - sum) / (n - cnt) sum * n cnt * totalif(sum*ncnt*total){constotherSumtotal-sum;console.log(1);console.log(Math.min(sum,otherSum)*5);return;}}}console.log(0);});Gopackagemainimport(bufiofmtos)funcmain(){in:bufio.NewReader(os.Stdin)out:bufio.NewWriter(os.Stdout)deferout.Flush()arr:make([]int,0)total:0varxintfor{_,err:fmt.Fscan(in,x)iferr!nil{break}arrappend(arr,x/5)totalx/5}n:len(arr)// 无法形成合法方案ifn2{fmt.Fprintln(out,0)return}// dp[cnt][sum]是否可以选出 cnt 个元素使元素和为 sumdp:make([][]bool,n1)fori:0;in;i{dp[i]make([]bool,total1)}dp[0][0]truefor_,x:rangearr{// 0/1 背包必须从大到小枚举forcnt:n;cnt1;cnt--{forsum:total;sumx;sum--{dp[cnt][sum]dp[cnt][sum]||dp[cnt-1][sum-x]}}}forcnt:1;cntn;cnt{forsum:0;sumtotal;sum{if!dp[cnt][sum]{continue}// 两个子集平均值相同// sum / cnt (total - sum) / (n - cnt) sum * n cnt * totalifsum*ncnt*total{otherSum:total-sum fmt.Fprintln(out,1)ifsumotherSum{fmt.Fprintln(out,sum*5)}else{fmt.Fprintln(out,otherSum*5)}return}}}fmt.Fprintln(out,0)}