# 前两题是贪心问题
首先，问题我就不贴了（因为不能传播，学习思路就好了，题目千变万化，华为本就没有原题），供大家参考思路。
# 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 这题不难，输入是真难顶
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 华为没有使用牛客答题了，用的实习知，不少人踩坑，考试过程在不能退出页面，考前个人信息填写任何一步出问题，都可能导致无法开启摄像头--判为作弊，所以要提前练习下模拟考试。
最后，若有侵权，我立即删帖。
全部评论
(3) 回帖