华为4.13笔试题解（附原题）
华为4.13技术笔试 原题在最后
题目1：服务器调度，优先级排序
题目2：工单选择策略，贪心+优先级队列
题目3：分糖果，0-1背包dp、求等和子集
第一题比较简单，先筛选出符合要求的服务器，再按不同的需求策略排序就可以。需要注意的是几个细节：1.arch=9/np=2时满足所有arch/np 2.输出按序号排序而不是优先级队列里的排序 3.着重注意输出空格
第二题首先按贪心的思想，用时间戳记录当前已用的时间，每次选择最近sla时间的分值最大的工单，这种做法可以ac30%，但是存在情况[(1,1),(2,10),(2,11)]用贪心得到11而答案是21。所以我们用一个最小堆来储存所有选择过的工单，称为chosen_list。每当有未完成的工单过期时，我们将此工单和chosen_list里最小分值的工单比较，若此工单大于chosen_list里的最小工单，则用此工单代替最小工单。这道题思路与力扣630课程表三非常接近，可以好好看看。
第三题所有糖果总数的一半为target，求等和子集。用dp[i][j]表示用前i袋糖（含i）能否凑到j块糖，答案即为dp[N][target]。递推公式dp[i][j] = dp[i-1][j - bags[i-1]] or dp[i-1][j]，bags[i-1]表示第i袋糖中的糖果数。初始化边界条件dp[:][0]=True即可，思路和力扣416完全一致。这道题还有一个问题是需要输出两个子集，dp的时候记录路径就行，可以把dp矩阵中的元素改成一个(真值，列表)对，即(is_possible, chosen)，is_possible为原dp矩阵的值表示能否凑足，chosen储存凑足所用的袋标号，递推公式变为：
if dp[i-1][j][0] == True:
dp[i][j] = dp[i-1][j]
elif dp[i-1][j - bags[i-1]] == True:
dp[i][j] = (True, dp[i-1][j - bags[i-1]][1] + [i])
else:
dp[i][j] = (False,[])
递推的时候注意列表的深拷贝（针对python玩家）
好像还有可回溯的DFS做法，懒得想了留给评论区补充
但是这道题好像判题的时候有问题？看牛客上的老哥们好多都是一顿操作猛如虎，一点提交百分之五（俺也一样），不知道是不是哪个细节没注意到，已经反馈给HR，看看那边怎么说
深夜睡不着起来码题解，脑子不太清醒，如果有错误欢迎老哥们指出
/***************************************************************************************************/
附原题题目：（按记忆写的可能有偏差）
第一题：
每个服务器有如下属性：index，cpuCount，memSize，arch=0~9，np=0~2
输入N行这样的服务器参数
输入1行需求，按如下格式：
策略s，需要服务器的数量m，cpu，mem，arch_，np_
符合要求的服务器要求：cpuCount >= cpu, memSize >= mem, arch == arch_, np == np_, 其中若np=2表示满足所有np要求，arch=9表示满足所有arch要求
有如下两种分配策略：
策略1：cpu优先，即优先分配符合要求的且具有最小cpuCount的服务器，再次按mem分配，再次按编号
策略2：mem优先，即优先分配符合要求的且具有最小memSize的服务器，再次按cpu分配，再次按编号
输出分配的服务器编号，如可分配的数量多于m则按上述策略排序选择前m个，若少于m个则输出全部符合要求的服务器，输出顺序按服务器编号排序
例：
输入：
5
0 4 330 4 1
1 3 300 0 1
2 5 500 0 1
3 4 350 9 1
4 6 340 0 2
1 2 3 330 0 1
输出：
2 3
第二题：
找到原题了，这个帖子里写的解法是错的
输入若干工单，每个包含SLA时间和score，即在规定SLA时间内完成该工单可以获得对应score，超时不得分，每个工单需要一个小时来完成，返回可以获得的最大得分
例：
输入：
5
1 3
1 5
3 5
4 5
3 2
输出：
15（完成第2,3,4个工单）
第三题：
现有若干袋糖果，想把这些糖果平分给两个小朋友，每袋糖果只能分给一个小朋友且不能拆开，返回每个小朋友分得的糖果数，每个小朋友分到的各袋糖果的糖果数，输出顺序不限，如不能平均分则直接输出-1（题目存疑）
输入为每袋糖果的糖果数量
例：
输入：
3 5 7 2 5 8
输出：
15
7 8
3 5 2 5
#华为笔试##春招##实习##笔试题目##笔经##Python##题解#
投递美团等公司10个岗位