华为七月份机试题总结1-0707
这些题目都是在牛客网上搜集的，也参考了一些大佬的代码。
对题目进行了详细的描述，并提供了输入输出示例，参考代码也更适合基础薄弱的参看。
希望大家可以一起交流学习，offer拿到手软！！！
/*
华为的机试题0707-1：
贪心做法
题目： 有n个事件，每个事件形式为(t,w),表示若在t时刻前完成该事件，获得w分数，每一个小时只能完成一个事件，求最大能获得的分数
事件数量<=1000000
输入：
7
1 6
1 7
3 2
3 1
2 8
2 10
6 1
输出：21
*/
#include<bits/stdc++.h>
using namespace std;
int main()
{
auto cmp = [](const vector<int> &a, const vector<int> &b)
{
// if(a[0] == b[0]) return a[1]>b[1];
// else return a[0]<b[0];
return a[0]<b[0];
};
int N;
cin>>N;
vector<vector<int>> nums;
vector<int> v_temp;
int a, b;
for(int i=0; i<N; i++)
{
cin>>a>>b;
v_temp.push_back(a);
v_temp.push_back(b);
nums.push_back(v_temp);
v_temp.clear();
}
sort(nums.begin(), nums.end(), cmp); //按时刻进行排序，对于时刻相同的，分值大的优先（实际这个没必要，因为接下来会用小顶堆替换掉以前时刻分值小的）
for(int i=0; i<nums.size();i++)
{
cout<<nums[i][0]<<':'<<nums[i][1]<<endl;
}
priority_queue<int,vector<int>, greater<int>> pq; //就是为了解决出现时刻相同的情况，如果分值大，则会替换以前时刻的工作
pq.push(nums[0][1]);
for(int i=1; i<nums.size(); i++)
{
cout<<"Top is"<<pq.top()<<endl;
if(nums[i][0] == nums[i-1][0]) //出现了时刻相等，就要判断相等时刻的分值是否比以前的大，如果是则直接替换掉
{
if(nums[i][1] > pq.top())
{
cout<<"Delete " <<pq.top()<<endl;
pq.pop();
pq.push(nums[i][1]);
}
}
else //对于不同时刻直接压入小顶堆就可以了
{
pq.push(nums[i][1]);
}
}
int result = 0;
while(!pq.empty())
{
result += pq.top();
pq.pop();
}
cout<<result<<endl;
return 0;
}
/*
华为的机试题0707-2：
图搜素
给定一个有向图以及一个起点，问是否只从起点出发就可以走到全部的点，如果可以，输出起点到其他点的最长距离
点数<=100， 边数<=5000，路径的长度小于100
输入：
[1,2,15]
[1,3,14]
[3,4,9]
4
1
输出：23； 路线1-3-4.虽然不经过2,但是1可以到2,所以算能到达。
输入如上，前三行分别代表景点1到景点2之间有路，距离为15,景点1到景点3之间有路，距离为14,景点3到景点4之间有路，距离为9。
接下来输入一共有多少个景点，下一行是起始景点。问是否能逛完，可以的话求最长路径，否则输出-1.景点数小于100,路径长度小于100,两个景点间路径数小于5000.
*/
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> graph(100, vector<int>(100, 0));
vector<bool> visited(100, false);
int max_path = 0;
void dfs(int start, int N, int path)
{
visited[start] = true;
for(int i=0; i<N; i++)
{
if(graph[start][i]>0 && !visited[i])
{
path += graph[start][i]; //这才是在深度方向上相加
dfs(i, N, path);
max_path = max(path, max_path);
path -= graph[start][i];
}
}
}
int main()
{
string s;
int start;
int N;
while(getline(cin, s))
{
// cout<<"s="<<s<<endl;
if(s[0] == '[')
{
s = s.substr(1, s.size()-2);
int i, j, val;
int pos = s.find(',');
i = stoi(s.substr(0, pos));
s = s.substr(pos+1);
pos = s.find(',');
j = stoi(s.substr(0, pos));
s = s.substr(pos+1);
val = stoi(s);
// cout<<"i="<<i<<";j="<<j<<";val="<<val<<endl;
graph[i-1][j-1] = val;
}
else
{
N = stoi(s);
cin>>s;
start = stoi(s)-1;
// cout<<"N="<<N<<";start="<<start<<endl;
break;
}
}
dfs(start, N, 0);
for(int i=0; i<N; i++)
{
if(!visited[i])
{
cout<<-1<<endl;
return 0;
}
}
cout<<max_path<<endl;
return 0;
}
/*
华为的机试题0707-3：
dfs暴搜就可以
题目： 题目大意：在中国象棋中，给出大小为m*n的棋盘，棋盘上有一些障碍点，以及一匹马在S处要到T点，
给出中国象棋中跳马的规则，问至少需要多少步才能跳到T点
数据范围m, n< = 150
输入： 对于输入的解释，4是行，5是列，#是障碍物，H是起始点，T是终止点
4
5
***#*
*H***
**T#*
#****
输出：从H到T最小的步数
4
*/
#include<bits/stdc++.h>
using namespace std;
int min_val = INT_MAX;
vector<int> directions_x = {2, 2, -2, -2, 1, 1, -1, -1};
vector<int> directions_y = {1, -1, 1, -1, 2, -2, 2, -2};
void dfs(vector<vector<char>> &graph, vector<vector<bool>> &visited, int i, int j, pair<int, int> end, int step)
{
if(i<0 || i>=graph.size() || j<0 || j>=graph[0].size() || visited[i][j] || graph[i][j] == '#')
{
return;
}
if(i == end.first && j == end.second)
{
min_val = min(step, min_val);
return;
}
visited[i][j] = true;
step++;
for(int k=0; k<8; k++)
{
int x = i+directions_x[k];
int y = j+directions_y[k];
dfs(graph, visited, x, y, end, step);
}
visited[i][j] = false;
step--;
}
int main()
{
int m, n;
cin>>m>>n;
vector<vector<char>> graph(m, vector<char>(n, '*'));
vector<vector<bool>> visited(m, vector<bool>(n, false));
char temp;
pair<int, int> start;
pair<int, int> end;
for(int i=0; i<m; i++)
{
for(int j=0; j<n; j++)
{
cin>>temp;
graph[i][j] = temp;
if(temp == 'H')
{
start.first = i;
start.second = j;
}
if(temp == 'T')
{
end.first = i;
end.second = j;
}
}
}
dfs(graph, visited, start.first, start.second, end, 0);
if(min_val == INT_MIN)
{
cout<<-1<<endl;
}
else
{
cout<<min_val<<endl;
}
return 0;
}
