华为秋招 2023.08.30 编程题目与题解

发表于 2023-08-30 分类于笔试阅读次数：本文字数： 2.4k 阅读时长 ≈ 2 分钟

1、智慧打卡系统

某家高科技公司为方便员工省去每日上下班的打卡操作，计划推广使月智慧打卡系统。其运行的原理是系统会记录员工当日进出门禁的时间（员工在上班期间可能会多次进出门禁，格式为24小时制，小时:分钟，"HH:MM"）。

现在请编写一个算法，计算员工当日的工作时长（单位：分钟），具要求如下:

单次离岗15min以内，不从工作时长中扣除
12:00至14:00为午休时间，不算工作时长
18:00至19:30为晚饭时间，不算工作时长

输入

第一行：员工当天进门禁的次数\(n\)。

第二行：员工当天进门禁的所有时间，以空格分隔。

第三行：员工当天出门禁的次数\(m\)。

第四行：员工当天出门禁的所有时间，以空格分隔。

注：\(0<n,m<100\)，不存在相同的出入门禁时间，也不存在连续的出门禁或入门禁的情况。

输出

当日的工作时长。

样例

输入：
5
07:50 08:50 12:30 13:40 19:50
5
08:45 12:20 13:20 18:30 20:30

输出：
530

提示：
员工的工作时段为07:50~12:00，14:00~18:00，19:50~20:30，工作时长为530分钟。

输入：
4
08:30 12:30 14:00 18:20
4
12:00 13:00 16:50 19:00

输出：
380

提示：
员工的工作时段为08:30~12:00，14:00~16:50，工作时长为380分钟。

解答

这道题的输入方式让我感到有一些奇怪，\(n=m\)不应该是必须成立的吗？然后直接按照这个假设继续做这道题了。

假设现在有\(n\)个入门时间和\(n\)个出门时间，那么首先将它们排好序，那么如果数据是正确的话，那么对于第\(i\)个上班\(l_i\)和第\(i\)个下班时间\(r_i\)，都有\(l_i<r_i\)且\(r_i< l_{i+1}\)。注意，一个上班时间段是\([l_i,r_i)\)，即左闭右开的。

接下来处理出每一对\((l_i,r_i)\)后，如果对于相邻两对\((l_i,r_i),(l_{i+1},r_{i+1})\)，满足\(l_{i+1}-r_i\le 15\)，那么将它们合并成一个上下班时间对\((l_i,r_{i+1})\)。

接下来枚举每个上班时间对中的每一分钟，如果不在吃饭时间，那么说明工作了一分钟，直接累计即可。

代码

def parse_time(s):
    h, m = s.split(':')
    return int(h) * 60 + int(m)


n = int(input())
ls = sorted(input().split())
m = int(input())
lt = sorted(input().split())
n = min(n, m)
lv = []
for i in range(n):
    st, ed = parse_time(ls[i]), parse_time(lt[i])
    while len(lv) > 0 and st - lv[-1][1] <= 15:
        st = lv[-1][0]
        lv.pop()
    lv.append((st, ed))

lunch_time = (parse_time("12:00"), parse_time("14:00"))
dinner_time = (parse_time("18:00"), parse_time("19:30"))
ans = 0
for l, r in lv:
    for t in range(l, r):
        if not (lunch_time[0] <= t < lunch_time[1] or dinner_time[0] <= t < dinner_time[1]):
            ans += 1
print(ans)

2、频率搬移值分配

在无线通信设备中通常使用超外差接收机，超外差接收机是利用本地产生的振荡波与输入信号混频，将输入信号频率变换为某个预先确定的频率的方法。也就是说，信号通过一个混频器后，频率就会搬移一个数值。在项目中由于要节省器件，混频器需要尽可能的共享，我们设计了二叉树型的混频器组，可以同时把信号搬移到不同的频率上。

二叉树为完全二叉树。我们给定二叉树的层数和从根节点开始到每个子节点的频率搬移总和，输出二叉树。

规则：节点的值为它的所有叶子节点的目标频率值最大最小值的平均值（非整数向下整）减去它所有父节点的总和。

输入

叶子节点的数目（必定是\(2^n\)），\(1\le\) 叶子节点的数目 \(\le 4096\)。
每个叶子节点的目标频率值，二叉树的数组形式表示，把二又树的结点依次自上而下，自左至右储存到数组中，\(0\le\) 目标频率值 \(\le1000000\)

输出

以数组形式的二叉树表示

样例

输入：
4
18 24 2 4

输出：
13 8 -10 -3 3 -1 1

提示：
第0层：所有叶子节点最大最小值的平均值为(2+24)/2=13所有父节点值为0，最终为13-0=13
第1层左节点：所有叶子节点最大最小值的平均值为(18+24)/2=21所有父节点值为13，最终为21-13=8
第1层右节点：所有叶子节点最大最小值的平均值为(2+4)/2-3所有父节点值为13，最终为3-13=-10
第2层第1个节点：所有叶子节点最大最小值的平均值为18/1=18所有父节点值为13+8=21，最终为18-21=-3
第2层第2个节点：所有叶子节点最大最小值的平均值为24/1=24所有父节点值为13+8=21，最终为24-21=3
第2层第3个节点：所有叶子节点最大最小值的平均值为2/1=2所有父节点值为13+(-10)=3，最终为2-3=-1
第2层第4个节点：所有叶子节点最大最小值的平均值为4/1=4所有父节点值为13+(-10)=3，最终为4-3=1

解答

由于这是一棵\(n\)层的完全二叉树。因此有\(2^{n+1}-1\)个节点。对于\(i\ge 2^n\)，节点\(i\)是叶子节点；其余节点是内部节点。那么假设题目中输入的是数组\(a\)中下标从\(2^n\)到\(2^{n+1}-1\)的值（\(i<2^n\)时\(a_i\)未定义）。

分别令\(\max_i,\min_i,s_i,v_i\)分别表示：

以\(i\)为子树中的所有叶子节点的频率最大值；
以\(i\)为子树中的所有叶子节点的频率最小值；
从根节点到第\(i\)个节点的值之和；
节点\(i\)的值。

如果\(i\ge 2^n\)，那么由于这课子树只有一个节点，因此有\(\max_i=\min_i=a_i\)；否则，当前子树的所有叶子节点最大值（最小值）要么来自左子树，要么来自右子树，因此有\(\max_i=\max\{\max_{2i},\max_{2i+1}\},\min_i=\min\{\min_{2i},\min_{2i+1}\}\)。由于\(i\)的父节点是\(\lfloor i/2\rfloor\)，并假设\(s_0=0\)，那么按照题目的定义，节点\(i\)的值\(v_i=\lfloor (\max_i+\min_i)/2\rfloor-s_{\lfloor i/2\rfloor}\)，并得到\(s_i=s_{\lfloor i/2\rfloor}+v_i\)。

代码

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=10004;
int a[N];
int v[N],mn[N],mx[N],s[N];
int main(){
    int n;
    scanf("%d",&n);
    int m=n*2-1;
    for(int i=m-n+1;i<=m;i++){
        scanf("%d",&a[i]);
        mx[i]=mn[i]=a[i];
    }
    for(int i=m-n;i>0;i--){
        mx[i]=max(mx[i<<1],mx[i<<1|1]);
        mn[i]=min(mn[i<<1],mn[i<<1|1]);
    }
    for(int i=1;i<=m;i++){
        v[i]=(mx[i]+mn[i])/2-s[i>>1];
        s[i]=s[i>>1]+v[i];
    }
    for(int i=1;i<=m;i++)
        printf("%d%c",v[i], " \n"[i==m]);
}

3、内存分配

系统由\(n\)个任务组成，任务运行有依赖关系，前序任务执行完毕才可以启动后续任务。任务在启动前申请内存，执行完毕后释放，内存释放后可用于其他任务使用。每个任务的运行时间相等。请计算系统所有任务执行所需要的最小内存。

输入

第\(1\)行为\(1\)个正整数\(n\)，表示任务个数，\(n<20\)

第\(2\)行为\(n\)个正整数，表示每个任务所需要的内存大小，\(0<\) 内存 \(<1000\)

第\(3\)行为\(n\)个取值为\(0\)或\(1\)的数，表示任务\(0\)对其他任务的依赖关系，\(0\)表不依赖，\(1\)表示依赖

……

第\(3+n-1\)行为\(n\)个取值为\(0\)或\(1\)的数，表示任务\(n-1\)对其他任务的依赖关系，\(0\)表示不依赖，\(1\)表示依赖

输出

输出系统任务执行所需要的最小内存

样例

输入：
9
50 50 80 40 40 40 60 60 60
0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0
0 0 1 0 0 1 0 0 0
0 0 0 1 0 0 0 0 0
0 1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 1 0

输出：
120

提示：
第一行：9，表示有9个任务
第二行：50 50 80 40 40 40 60 60 60，表示任务t0~t8需要的内存大小
第三行：0 0 0 0 0 0 0 0 0，表示t0不依赖任务其他任务
第四行：1 0 0 0 0 0 0 0 0，表示t1依赖t0
第五行：0 1 0 0 0 0 0 0 0，表示t2依赖t1

...

1)执行t0，分配m0=50，占用空间[0,50)，最大访问地址为50
2)执行t1，分配m1=50，占用空间[0,50)，最大访问地址为50
3)并发执行t2和t5，分配m2=80，m5=40，占用空间[0,120)，最大访问地址为120
4)执行t3，分配m3=40，占用空间[0.40)，最大访问地址40
5)并发执行t4和t7，分配m4=40，m7=60，占用空间[0,100)，最大访问地址为100
6)执行t6，分配m6=60，占用空间[0.60)，最大访问地址60
7)执行t8，分配m8=60，占用空间[0,60)，最大访问地址60
输出系统的需要的最小内存为120

输入：
10
40 50 80 10 30 80 90 30 70 150
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 1 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 1 0

输出：
170

提示：
输出系统的需要的最小内存为170

以下是两个样例的依赖图：

解答

题目已经给定了假设：所有任务的执行时间相等，因此整个任务执行过程中，任务都是一批一批地同时开始，同时结束。我们只需要知道每一个任务在哪一批进行即可，最终同一批的内存之和对最大值即为答案。

节点\(i\)对应的任务\(t_i\)在第\(k\)批执行当且仅当终点为\(i\)的最长路径的长度为\(k\)。因此整个过程使用拓扑排序即可完成。

为了更清晰化每一个匹配，接下来对拓扑排序的实现是用了两个数组来实现队列。对于同一个数组中的所有任务，它们都会在同一批次执行。

代码

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1004;
int d[N],a[N];
vector<int>g[N];
int n;
int main(){
    int x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&x);
            if(x){
                ++d[i];
                g[j].push_back(i);
            }
        }
    }
    int ans=0;
    vector<int>v1;
    for(int i=1;i<=n;i++)
        if(d[i]==0) v1.push_back(i);
    while(!v1.empty()){
        vector<int>v2;
        int s=0;
        for(int u:v1) s+=a[u];
        ans=max(ans,s);
        for(int u:v1){
            for(int v:g[u]){
                if(--d[v]==0){
                    v2.push_back(v);
                }
            }
        }
        v1=v2;
    }
    printf("%d\n",ans);
}