企业官网建设流程全解析

流量均衡控制

华为笔试真题 8月19号 非AI方向第三题 300分题型

题目内容

某厂商生产的交换机需要对用户的信息进行处理：按照信息的类别划分优先级，并为每种流量类型设置权重，用于在同优先级的场景下，让设备优先处理权重更高的消息。具体分类如下：

假设某台交换机当前由 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

题解

思路

思路:动态规划

1. 共有n个元素，总权重和为T，存在合法两个子数组的平均值相等。必定满足以下条件
   • 其中一个子数组个数为cnt, 元素和为sum
   • sum / cnt = (T - sum) / (n - cnt)=>sum * n = cnt * T
2. 基于1的分析使用动态规划定义dp[cnt][sum]表示是否可以选出 cnt 个元素，使它们的和为 sum
3. 然后使用01背包算法推导出所有存在的cnt,sum状态情况。
4. 然后判断遍历dp数组，在dp[cnt][sum]为true的情况，看是否满足sum / cnt = (T - sum) / (n - cnt)=>sum * n = cnt * T的情况，满足输出对应结果即可。

C++

#include<bits/stdc++.h>usingnamespacestd;intmain(){ios_base::sync_with_stdio(false);cin.tie(nullptr);vector<int>arr;intx;inttotal=0;while(cin>>x){arr.push_back(x/5);total+=x/5;}intn=arr.size();// 无法形成合法方案if(n<2){cout<<0;return0;}// dp[cnt][sum]：是否可以选出 cnt 个元素，使元素和为 sumvector<vector<bool>>dp(n+1,vector<bool>(total+1,false));dp[0][0]=true;for(intx:arr){// 0/1 背包，必须从大到小枚举for(intcnt=n;cnt>=1;cnt--){for(intsum=total;sum>=x;sum--){dp[cnt][sum]=dp[cnt][sum]|dp[cnt-1][sum-x];}}}for(intcnt=1;cnt<n;cnt++){for(intsum=0;sum<=total;sum++){if(!dp[cnt][sum]){continue;}// 两个子集平均值相同// sum / cnt = (total - sum) / (n - cnt) => sum * n == cnt * totalif(sum*n==cnt*total){intotherSum=total-sum;cout<<1<<endl;cout<<min(sum,otherSum)*5<<endl;return0;}}}cout<<0<<'\n';return0;}

java

importjava.io.*;importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args)throwsException{BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));StringBuildersb=newStringBuilder();Stringline;while((line=br.readLine())!=null){sb.append(line).append(" ");}String[]input=sb.toString().trim().split("\\s+");List<Integer>arr=newArrayList<>();inttotal=0;for(Stringstr:input){intx=Integer.parseInt(str);arr.add(x/5);total+=x/5;}intn=arr.size();// 无法形成合法方案if(n<2){System.out.println(0);return;}// dp[cnt][sum]：是否可以选出 cnt 个元素，使元素和为 sumboolean[][]dp=newboolean[n+1][total+1];dp[0][0]=true;for(intx:arr){// 0/1 背包，必须从大到小枚举for(intcnt=n;cnt>=1;cnt--){for(intsum=total;sum>=x;sum--){dp[cnt][sum]=dp[cnt][sum]||dp[cnt-1][sum-x];}}}for(intcnt=1;cnt<n;cnt++){for(intsum=0;sum<=total;sum++){if(!dp[cnt][sum]){continue;}// 两个子集平均值相同// sum / cnt = (total - sum) / (n - cnt) => sum * n == cnt * totalif(sum*n==cnt*total){intotherSum=total-sum;System.out.println(1);System.out.println(Math.min(sum,otherSum)*5);return;}}}System.out.println(0);}}

python

importsys data=sys.stdin.read().split()arr=[]total=0forvalueindata:x=int(value)arr.append(x//5)total+=x//5n=len(arr)# 无法形成合法方案ifn<2:print(0)sys.exit()# dp[cnt][sum]：是否可以选出 cnt 个元素，使元素和为 sumdp=[[False]*(total+1)for_inrange(n+1)]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(total+1):ifnotdp[cnt][sum_value]:continue# 两个子集平均值相同# sum / cnt = (total - sum) / (n - cnt) => sum * n == cnt * totalifsum_value*n==cnt*total:other_sum=total-sum_valueprint(1)print(min(sum_value,other_sum)*5)sys.exit()print(0)

javascript

constreadline=require('readline');constrl=readline.createInterface({input:process.stdin,output:process.stdout});constinput=[];rl.on('line',line=>{input.push(line);});rl.on('close',()=>{constdata=input.join(' ').trim().split(/\s+/);constarr=[];lettotal=0;for(constvalueofdata){constx=Number(value);arr.push(Math.floor(x/5));total+=Math.floor(x/5);}constn=arr.length;// 无法形成合法方案if(n<2){console.log(0);return;}// dp[cnt][sum]：是否可以选出 cnt 个元素，使元素和为 sumconstdp=Array.from({length:n+1},()=>newArray(total+1).fill(false));dp[0][0]=true;for(constxofarr){// 0/1 背包，必须从大到小枚举for(letcnt=n;cnt>=1;cnt--){for(letsum=total;sum>=x;sum--){dp[cnt][sum]=dp[cnt][sum]||dp[cnt-1][sum-x];}}}for(letcnt=1;cnt<n;cnt++){for(letsum=0;sum<=total;sum++){if(!dp[cnt][sum]){continue;}// 两个子集平均值相同// sum / cnt = (total - sum) / (n - cnt) => sum * n == cnt * totalif(sum*n===cnt*total){constotherSum=total-sum;console.log(1);console.log(Math.min(sum,otherSum)*5);return;}}}console.log(0);});

Go

packagemainimport("bufio""fmt""os")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}arr=append(arr,x/5)total+=x/5}n:=len(arr)// 无法形成合法方案ifn<2{fmt.Fprintln(out,0)return}// dp[cnt][sum]：是否可以选出 cnt 个元素，使元素和为 sumdp:=make([][]bool,n+1)fori:=0;i<=n;i++{dp[i]=make([]bool,total+1)}dp[0][0]=truefor_,x:=rangearr{// 0/1 背包，必须从大到小枚举forcnt:=n;cnt>=1;cnt--{forsum:=total;sum>=x;sum--{dp[cnt][sum]=dp[cnt][sum]||dp[cnt-1][sum-x]}}}forcnt:=1;cnt<n;cnt++{forsum:=0;sum<=total;sum++{if!dp[cnt][sum]{continue}// 两个子集平均值相同// sum / cnt = (total - sum) / (n - cnt) => sum * n == cnt * totalifsum*n==cnt*total{otherSum:=total-sum fmt.Fprintln(out,1)ifsum<otherSum{fmt.Fprintln(out,sum*5)}else{fmt.Fprintln(out,otherSum*5)}return}}}fmt.Fprintln(out,0)}