华为七月份机试题总结3-0721
对题目进行了详细的描述，并提供了输入输出示例，参考代码也更适合基础薄弱的参看。
希望大家可以一起交流学习，offer拿到手软！！！
/*
华为的机试题0721-1：
贪心做法
题目： 第一行输入 [车站数，乘客数]，
后面每一行输入 [上车时间，上车车站，下车车站]。
道路为环形道路，按最短路径行驶。比如车站0到车站10（共11个车站）选择0-10-9的路径。每一站路耗时5分钟，问路上最多同时有几辆车？
输入：
11 3
1 3 10
1 5 6
7 2 4
输出：
思路：因为这道题是要求在路上同时有多少辆车，也就是车在路上的时间间隔的最大重叠个数。
比如 乘客1：[5, 10], 乘客2 [6, 11],那么他们两个在[6,10]这个时间段都会在路上
因此只需要将上车时间，上车车站，下车车站转换为在路上的时间间隔就可以了
剩下的就是求重叠区间的问题了，和leetcode上射气球，合并重叠区间这类问题就相似了
*/
#include<bits/stdc++.h>
using namespace std;
int main()
{
auto cmp =[](const vector<int> &a, const vector<int> &b)
{
return a[0] < b[0];
};
int m, n;
cin>>m>>n;
int a, b, c;
vector<vector<int>> nums;
for(int i=0; i<n; i++)
{
//将原始输入转换为在路上的时刻区间
cin>>a>>b>>c;
vector<int> temp;
temp.push_back(a);
int time = 5 *(min(abs(b-c), m-(abs(b-c)))) + a;
temp.push_back(time);
nums.push_back(temp);
}
sort(nums.begin(), nums.end(), cmp);
for(int i=0; i<nums.size();i++)
{
cout<<nums[i][0]<<':'<<nums[i][1]<<endl;
}
int r_bound = nums[0][1];
int max_val = 0;
int val = 1;
for(int i=1; i<nums.size(); i++)
{
if(nums[i][0] < r_bound)
{
val++;
r_bound = min(r_bound, nums[i][1]);
}
else
{
val = 1;
r_bound = nums[i][1];
}
max_val = max(val, max_val);
}
cout<<max_val<<endl;
return 0;
} /*
华为的机试题0721-2：
贪心做法
题目： 有N个机器，K个任务。一个机器只能完成一个任务，
接下来输入K行，代表K个任务，第一个数字代表任务花费的时间，第二个数字代表任务的优先级。
优先级越小越优先，同优先级情况下花费时间越长越优先。问搞完这一批任务需要多长时间？
输入：
3 5
3 2
4 1
5 3
6 4
1 5
输出： 9
*/
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n, k;
cin>>n>>k;
vector<vector<int>> nums;
for(int i=0; i<k; i++)
{
int a, b;
cin>>a>>b;
nums.push_back({a, b});
}
auto cmp=[](const vector<int> &a, vector<int> &b){
return a[1] < b[1];
};
sort(nums.begin(), nums.end(), cmp); //按照优先级进行排序
int i=0;
//先将前n个任务加入小顶堆中,该小顶堆维护的是n台机器
priority_queue<int, vector<int>, greater<int>> pq;
for(; i<n; i++)
{
pq.push(nums[i][0]);
}
while(i<nums.size()) //将剩下的任务依次加入小顶堆的最小值中
{
int temp = pq.top() + nums[i][0];
pq.pop();
pq.push(temp);
i++;
}
int res=0; //小顶堆中的最大值即为所要花费的最长时间
while(!pq.empty())
{
res = max(res, pq.top());
pq.pop();
}
cout<<res<<endl;
return 0;
} /*
华为的机试题0721-3(dfs)：
图搜索,感觉和 0707-3基本一样，只不过数据处理比较麻烦，并且也没有告诉节点的个数。
题目： 就是给个有向图，无环，求最长路径。
n个点(n<=200)
输入：
[[1,2,5],[1,3,5],[2,3,10]]
输出： 15
*/
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> graph(201, vector<int>(201, 0));
int max_val = INT_MIN;
void dfs(vector<vector<int>> &graph, int s, unordered_set<int> u_s, int res)
{
for(auto &t:u_s)
{
if(graph[s][t] != 0)
{
res += graph[s][t];
max_val = max(max_val, res);
dfs(graph, t, u_s, res);
res -= graph[s][t];
}
}
}
int main()
{
vector<vector<int>> graph(201, vector<int>(201, 0));
unordered_set<int> us; //用于存放节点值
string s;
cin>>s;
//字符串的处理
while(s.size()>3)
{
int pos1 = s.find(']');
string temp = s.substr(2, pos1-2);
int a, b, c;
int pos2 = temp.find(',');
a = stoi(temp.substr(0, pos2));
temp = temp.substr(pos2+1);
us.emplace(a-1);
pos2 = temp.find(',');
b = stoi(temp.substr(0, pos2));
temp = temp.substr(pos2+1);
us.emplace(b-1);
c = stoi(temp);
graph[a-1][b-1] = c;
// cout<<"a="<<a<<"b="<<b<<"c="<<c<<endl;
s = s.substr(pos1+1);
}
for(auto &s:us) //这里有个疑问，就是节点是不是连续的从1-N,如果是直接传入us.size()就可以了
{
dfs(graph, s, us, 0);
}
cout<<max_val<<endl;
return 0;
} /*
华为的机试题0721-3(bfs)：
图搜索,感觉和 0707-3基本一样，只不过数据处理比较麻烦，并且也没有告诉节点的个数。
题目： 就是给个有向图，无环，求最长路径。
n个点(n<=200)
输入：
[[1,2,5],[1,3,5],[2,3,10]]
输出： 15
*/
#include<bits/stdc++.h>
using namespace std;
int max_val = INT_MIN;
void bfs(vector<vector<int>> &graph, int start, unordered_set<int> &us)
{
queue<pair<int, int>> q;
q.push(make_pair(start, 0));
while(!q.empty())
{
pair<int, int> cur = q.front();
q.pop();
for(auto &t2:us)
{
if(graph[cur.first][t2] !=0)
{
pair<int, int> add_val = make_pair(t2, graph[cur.first][t2] + cur.second);
max_val = max(max_val, add_val.second);
q.push(add_val);
}
}
}
}
int main()
{
vector<vector<int>> graph(201, vector<int>(201, 0));
vector<bool> visited(201, false);
unordered_set<int> us; //用于存放节点值
string s;
cin>>s;
//字符串的处理
while(s.size()>3)
{
int pos1 = s.find(']');
string temp = s.substr(2, pos1-2);
int a, b, c;
int pos2 = temp.find(',');
a = stoi(temp.substr(0, pos2));
temp = temp.substr(pos2+1);
us.emplace(a-1);
pos2 = temp.find(',');
b = stoi(temp.substr(0, pos2));
temp = temp.substr(pos2+1);
us.emplace(b-1);
c = stoi(temp);
graph[a-1][b-1] = c;
// cout<<"a="<<a<<"b="<<b<<"c="<<c<<endl;
s = s.substr(pos1+1);
}
for(auto &t1:us) //这里有个疑问，就是节点是不是连续的从1-N,如果是直接传入us.size()就可以了
{
bfs(graph, t1, us);
}
cout<<max_val<<endl;
return 0;
} 
腾讯一面977人在聊