华为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

第二题：

找到原题了，这个帖子里写的解法是错的

华为优招机试（2021年7月7）_柠檬の夏的博客-CSDN博客_华为机试2021

输入若干工单，每个包含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