7.21华为笔试

# 前两题是贪心问题

首先，问题我就不贴了（因为不能传播，学习思路就好了，题目千变万化，华为本就没有原题），供大家参考思路。

# 1 最少的汽车数量

这个题很有意思，眼看着是活动安排问题，当时没绕不出来。不妨这么想

1. 假定你知道活动安排问题。

2. 活动安排问题是指，一个共享会议室，安排了k个活动，每个活动都有起始时间startTime和结束时间endTime。当然这k个活动有重叠，没有重叠就能安排k个活动，求最大安排的活动数量？

3. 把这个思想放在这里，假如这k个APP请求，最多相容安排数量为ans，换句话说，这ans个请求只需要1辆车。

4. 将步骤3中的APP请求剔除，再一次执行最多相容安排问题，又需要1辆车

5. 直到ans为0，轮询的次数就是答案。

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

int main(int argc, char *argv[]) 
{
    int n, k;
    while (cin >> n >> k) {
        vector<vector<int>> nums(k);
        int start, upID, downID;
        for (int i = 0; i < k; ++i) {
            cin >> start >> upID >> downID;
            int temp = abs(upID - downID);
            nums[i].push_back(start);
            nums[i].push_back(start + min(temp, n - temp) * 5);
        }

        /**<按照结束时间升序排序 */
        sort(nums.begin(), nums.end(), [](const vector<int>& a, vector<int>& b){
           return a[1] < b[1];
        });

        vector<int> vis(k, 0);          /**<标记是否移除该任务 */
        int remain = k;
        int lastBegin = 0;              /**<相容任务剔除后，下一个起点在不断前进 */

        /**<1. 求解最大相容任务数量 使用一辆车 */
        /**<2. 剔除上次任务再求最大相容任务数量 使用一辆车 */
        /**<3. 重复2，直到任务为0 */
        int minCar = 0;
        while (remain > 0) {
            int i = lastBegin;
            while (vis[i] != 0)   ++i;        /**<找到第一个未移除的结点 */
            lastBegin = i;

            int endTime = nums[i][1];
            vis[i] = 1;
            int ans = 1;                      /**<活动至少安排一个 */
            for (++i; i < k; ++i) {
                if (vis[i]==0 && nums[i][0]>=endTime) {
                    endTime = nums[i][1];
                    ++ans;
                    vis[i] = 1;
                }
            }
            remain -= ans;                      /**<剔除当前相容的任务 */
            ++minCar;
        }
        cout << minCar << '\n';
    }

    return 0;
}




#if 0
50 3
0 0 5
10 10 11
25 20 40
output: 2

10 3
0 0 1
5 0 9
10 0 1
output: 1

15 8
0 6 12
5 0 3
15 5 7
15 8 13
20 12 15
25 7 11
30 0 11
40 5 8
output: 4

#endif

注意：一共有三组测试数据，第三组是我自己想的，有问题可以留言

备注：这题是一个改编题

253. 会议室 II

网友提出了一个很经典的解法，官方也提出了优先队列的解答方式

借用这种解法，可以把时间复杂度降低到O(nlogn)

int main(int argc, char *argv[]) 
{
    int n, k;
    while (cin >> n >> k) {
        vector<vector<int>> nums(k);
        int start, upID, downID;
        for (int i = 0; i < k; ++i) {
            cin >> start >> upID >> downID;
            int temp = abs(upID - downID);
            nums[i].push_back(start);
            nums[i].push_back(start + min(temp, n - temp) * 5);
        }
        
        vector<pair<int,int>> info;
        for (const auto& e : nums) {
            info.push_back({e[0], 1});
            info.push_back({e[1], -1});
        }
        sort(info.begin(), info.end());

        int minCar = 0;
        int number = 0;
        for (const auto& e : info) {
            number += e.second;
            minCar = max(minCar, number);
        }
        cout << minCar << '\n';
    }

    return 0;
}

# 2 一批任务需要多长时间？

这题也是贪心，比较简单，

1. 按照题目的优先级对数组排序

2. 由于机器数量n有限制，如果没有限制，那么最长时间就是最长的那个任务

3. 那么问题来了，机器少任务多，怎么办？

4. 用一个数组cost存下前n个任务，因为只有n个机器

5. 之后，遍历的每个时长加在cost数组的最小值上

6. 结果就是数组cost的最大值

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

int main(int argc, char *argv[]) 
{
    int n, k;
    while (cin >> n >> k) {
        vector<vector<int>> nums(k);
        int t, p;
        for (int i = 0; i < k; ++i) {
            cin >> t >> p;
            nums[i].push_back(t);
            nums[i].push_back(p);
        }
        
        /**<按照第二列升序排序，相同按照第一列降序 */
        sort(nums.begin(), nums.end(), [](const vector<int>& a, vector<int>& b) {
            return a[1]!=b[1] ? a[1]<b[1] : a[0]>b[0];
        });

        /**<机器足够多 */
        if (n >= k) {
            int ans = 0;
            for (int i = 0; i < k; ++i)
                ans = max(ans, nums[i][0]);
            cout << ans << '\n';
        }

        /**<初始化n台机器 */
        vector<int> cost(n, 0);
        int i = 0;
        while (i < n) {
            cost[i] = nums[i][0];
            ++i;
        }
        /**<给最小值加上当前值-贪心 */
        while (i < k) {
            *min_element(cost.begin(), cost.end()) += nums[i++][0];
        }
        cout << *max_element(cost.begin(), cost.end()) << '\n';
    }

    return 0;
}


#if 0
3 7
1 1
4 1
5 3
4 2
2 1
3 3
2 1
output: 8


#endif

# 3 图中最长路径

这题不难，输入是真难顶

1. 解析输入

[[1,2,5],[1,3,5],[2,5,5],[3,7,10],[3,4,10],[4,2,10],[4,7,5],[5,6,5],[6,7,5]]

有两个基本问题?

（1）图的边集未知？

（2）图的点数未知？
我没有采用传统的切割方式，我换了一种方式

（1）把", [ ]"替换成空格

（2）将新的字符串存入istringstream

（3）每次读取三个整数即可

求解图中最大的路径长度

（1）首先，图中有没有环？我的代码没有考虑环，当然dfs可以解决环，只是最长路径有环的话可以多绕几圈，，，就没有最大值了

（2）之后对每一个结点dfs找出最大路径和，就暴力搜索

（3）这里存储图有技巧，因为实际上图的存储常用邻接表，它是链表，考试中没有那么多时间写出来；如果用邻接矩阵的话，三维，可能超时。

问题：把邻接表存入矩阵中？

struct Node {
    int to, weight;
};
const int MAXSIZE = 210;
vector<Node> G[MAXSIZE];

1. 起点其实是数组的下标，把终点和权重存入Node即可

2. 上面的G后面是中括号，它其实是二维矩阵，和

G(MAXSIZE)

有区别。

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

struct Node {
    int to, weight;
};
const int MAXSIZE = 210;
vector<Node> G[MAXSIZE];

int dfs(int u) {
    int ans = 0;
    for (const auto&e : G[u]) {
        ans = max(ans, dfs(e.to) + e.weight);
    }
    return ans;
}

int main(int argc, char *argv[]) 
{
    string str;
    while (cin >> str) {
        for (auto& e : str) {
            if (e==',' || e=='[' || e==']')
                e = ' ';
        }
        istringstream iss(str);
        int a, b, c;
        int points = 0;                             /**<图中节点数 */
        while (iss >> a >> b >> c) {
            points = max(points, max(a, b));
            G[a].push_back({b, c});
        }

        int ans = 0;
        for (int i = 1; i <= points; ++i) {
            ans = max(ans, dfs(i));
        }
        cout << ans << '\n';
    }

    return 0;
}


#if 0
[[1,2,5],[1,3,5],[2,5,5],[3,7,10],[3,4,10],[4,2,10],[4,7,5],[5,6,5],[6,7,5]]
output: 40

#endif

华为没有使用牛客答题了，用的实习知，不少人踩坑，考试过程在不能退出页面，考前个人信息填写任何一步出问题，都可能导致无法开启摄像头--判为作弊，所以要提前练习下模拟考试。

最后，若有侵权，我立即删帖。

#华为笔试##笔经##华为#