2023 华为笔试题 0412

笔试时间：2023年4月12日暑期实习

备注：只有前两题

第一题

题目：交易系统的降级策略

有一个核心交易系统接口被N个上游系统调用，每个上游系统的调用量R=[R1,R2.....,RN]，由于核心交易系统集群故障，需要暂时系统降级限制调用，核心交易系统能接受的最大调用量为cnt。设置降级规则如下：

如果sum(R1.R2..RN)小于等于cnt，则全部可以正常调用，返回-1;如果sum(R1.R2....RN)大于cnt，设置一个闻值limil，如果某个上游系统发起的调用量超过limt，就将该上游系统的调用量限制为limit，其余未达到limit的系统可以正常发起调用。

求出这个最大的lmit (mit可以为0)此题目对效率有要求，请选择高效的方式。

解答要求：时间限制:C/C++ 1000ms,其他语言: 2000ms 内存限制:C/C++200MB其他语言:400MB

输入描述

第一行:每个上游系统的调用量(整型数组)

第二行:核心交易系统的最大调用量

0<R.length<=10^5，0<R[i]<105，0<cnt <= 10^9

输出描述

调用量的阈值Iimit

样例输入

示例1:

1 4 2 5 5 1 6

13

示例2:

1 7 8 8 1 0 2 4 9

7

样例输出

示例1:

2（因为1+4+2+5+5+1+6>13;将limit设置为2，则1+2+2+2+2+1+2=12<13。所以imit为2）

示例2:

0（因为即使imil设置为1,1+1+1+1+1+1+1+1=8>7也不满足，所以limit只能为0）

参考题解

对limit进行二分。

Python：[此代码未进行大量数据的测试，仅供参考]

R = [int(c) for c in input().split(" ")]
cnt = int(input())

def check(x):
    res = 0
    for r in R:
        if r <= x: res += r
        else: res += x
    return res <= cnt

l, r = 0, 10**5
while l < r:
    mid = (l + r + 1) >> 1
    if check(mid):l = mid
    else: r = mid - 1

print(r)

第二题

题目：获取最多食物

主办方设计了一个获取食物的游戏。游戏的地图由N个方格组成，每个方格上至多2个传送门，通过传送门可将参与者传送至指定的其它方格。同时，每个方格上标注了三个数字:

1、第一个数字id:代表方格的编号，从0到N-1，每个方格各不相同

2、第二个数字parent-id:代表从编号为parent-id的方格可以通过传送门传送到当前方格(-1则表示没有任何方格可以通过传送门传送到此方格，这样的方格在地图中有且仅有一个;

3、第不个数字value: 取值在[100，100]的整数值，正整数代表参与者得到相队取值单位的食物，负整数代表失去相应数值单位的食物(参与者可能存在临时持有食物为负数的情况)，0则代表无变化。

此外，地图设计时保证了参与者不可能到达相同的方格两次，并且至少有一个方格的value是正整数。游戏开始后，参与者任意选择一个方格作为出发点，当遇到下列情况之一退出游戏: (1)参与者当前所处的方格无传送门: (2) 参与者在任意方格上丰动宣布退出游戏。请计算参与者退出游戏后，最多可以获得多少单位的食物。

解答要求：时间限制: C/C++ 1300ms.其他语言:2600ms内存限制: C/C++256MB其他语言:512MB 第一行:方块个数N (N<10000)