2024秋招华为机试题目记录(2023.8.30)

第一题（100分）

设计一个自动计算打卡时间的程序。输入：员工一天多次进出公司的时间点。输出：总有效工作时间。

• 如果离开公司在15分钟以内，不从总时长中扣除
• 12:00-14:00,18:00-19:30是午休和晚餐时间，不算工作时间

输入描述：

第一行:员工当天进门禁的次数n。

第二行:员工当天进门禁的所有时间，以空格分隔。（24小时制，格式为xx:xx）

第三行:员工当天出门禁的次数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

My answer:

#include<iostream>
#include<vector>

using namespace std;

int main()
{
    int in,out;
    cin >> in;
    vector<int> in_time(in);
    string str;
    int time;
    for(int i = 0; i < in; i++)
    {
        cin >> str;
        time = stoi(str.substr(0,2)) * 60 + stoi(str.substr(3));
        if(time>12*60 && time<=14*60)time=14*60;
        else if(time>18*60 && time<=195*6)time=195*6;
        in_time[i] = time;
    }
    cin >> out;
    vector<int> out_time(out);
    for(int i = 0; i < out; i++)
    {
        cin >> str;
        time = stoi(str.substr(0,2)) * 60 + stoi(str.substr(3));
        if(time>=12*60 && time<14*60)time=12*60;
        else if(time>=18*60 && time<195*6)time=18*60;
        out_time[i] = time;
    }
    
    int time_sum = out_time[out-1] - in_time[0];
    if(out_time[out-1]>=195*6 && in_time[0]<=18*60)time_sum -= 90;
    if(out_time[out-1]>=14*60 && in_time[0]<=12*60)time_sum -= 120;
        
    for(int i = 1; i < in; i++)
    {
        int back = in_time[i];
        int leave = out_time[i-1];
        int leave_time = back - leave;
        if(leave_time <= 15)continue;
        if(back>=195*6 && leave<=18*60)leave_time -= 90;
        if(back>=14*60 && leave<=12*60)leave_time -= 120;
        if(leave_time > 0)
            time_sum -= leave_time;      
    }
    if(time_sum <0)
        time_sum = 0;
    cout << time_sum <<endl;

    return 0;

思路： (1) 读入时间的时候，进入的时间如果在休息时间内，就设成休息时间的结束。如果离开时间在休息时间内，就设成休息时间的开始。 (2) 总时间首先是最后离开的时间减去一开始进入的时间。再根据起止时间的范围，判断是否减去午休和晚餐的时间。 (3) 再考虑中间每次离开，如果大于15分钟，就从总时长中减去

第二题（200分）

已知一棵完全二叉树，满足每个结点的值是它的叶结点频率的最大值加最小值除以2减去它的父节点的值之和。给定叶节点的个数和频率，求这个完全二叉树。

如：

输入节点数4，输入四个节点的频率。根节点的叶节点为4个节点，四个节点的最大值加最小值除以2，再减去其根节点（没有根节点），得到13。其他节点同理，可以看到计算完成后，每一个根节点到叶节点的值之和是该叶节点的频率。

输入描述：

第一行：叶节点个数。一定是2的n次。

第二行：每个叶节点的频率，0 < x < 1000000

输出描述：

二叉树的层序遍历，注意最后不能有空格

样例输入：

4
18 24 2 4

输出：

13 8 -10 -3 3 -1 1

My answer:

#include<iostream>
#include<vector>

using namespace std;

void get_max_min(vector<int>& leaf, int left, int num, int& max, int &min)
{
    min = leaf[left];
    max = leaf[left];
    for(int i = left+1; i < left+num; i++)
    {
        min = min < leaf[i] ? min : leaf[i];
        max = max > leaf[i] ? max : leaf[i];
    }
}


int main()
{
    int n;
    cin >> n;
    vector<int> leaf(n);
    int max = 0, min = 1000000;
    for(int i = 0; i < n; i++)
    {
        cin >> leaf[i];
    }
    int layers = int(log(n)/log(2)) + 1;
    std::vector<int> fathers, fathers_tmp;
    for(int i = 0; i < layers; i++)
    {
        int num = n / pow(2,i);
        for(int j = 0;j<pow(2,i);j++)
        {
            int value;
            if(i != layers - 1){
                int min,max;
                get_max_min(leaf, num*(j), num, max, min);
                value  = (max+min)/2;
            }
            else
                value = leaf[j];
            fathers_tmp.push_back(value);
            if(fathers.size()!=0) value -= fathers[j/2];
            if(j==n-1)cout << value << endl;
            else
                cout << value << " ";
        }
        fathers.assign(fathers_tmp.begin(),fathers_tmp.end());
        fathers_tmp.clear();
    }    
    return 0;
}

思路： 从根节点开始按层计算。对每个节点，确定节点对应的叶节点，找到最大值最小值。同时保存上一层所有节点的父节点值加上本节点的值之和。

第三题（300分）

有n个任务，任务之间有依赖关系（只有做完任务A，才能做任务B），每个任务需要不同内存，在尽快完成所有任务的情况下需要的最小内存是多少

输入描述：

第一行：任务个数

第二行：每个任务占用内存量

第3~3+n行：任务之间的依赖关系

输出描述：

需要的最小内存

这题没做完，案例也没有记录下来。拓扑排序相关之前做的比较少，如果有时间需要刷一刷这类题。