华为七月份机试题总结4-0728
这些题目都是在牛客网上搜集的，也参考了一些大佬的代码。
对题目进行了详细的描述，并提供了输入输出示例，参考代码也更适合基础薄弱的参看。
希望大家可以一起交流学习，offer拿到手软！！！
/*
华为的机试题0728-1：
题目： 服务器
输入
4
0,2,200,0,1
1,3,400,0,1
2,3,400,1,0
3,3,300,0,1
3,1,3,200,0,1
输出
//2 1 3
第一行输入服务器个数M
接下来M行为服务器参数，按顺序为编号，cpu数，内存大小， 架构， 是否支持NP卡
最后一行为选择要求， 按顺序为服务器数， 选择策略， cpu数，内存大小，架构， NP
(服务器cpu数内存应不小于要求， 架构NP必须一致)
其中架构0-8 为9则都可以
NP 0-1 为2则都可以
选择策略：
为1时 cpu优先， 优先最符合的cpu数，在选最符合的内存大小
为2时 内存优先， 优先最符合的内存大小，在选最符合的cpu数
cpu数内存大小一样时，按编号大小选
输出说明， 选两台， 分别为1,3
*/
#include<bits/stdc++.h>
using namespace std;
//定义一个服务器的结构体来存放服务器的相关参数
struct Server
{
int _index;
int _n_cpu;
int _n_mem;
int _arch;
int _np;
Server(int index, int n_cpu, int n_mem, int arch, int np):_index(index), _n_cpu(n_cpu), _n_mem(n_mem), _arch(arch), _np(np)
{
};
};
int main()
{
int N;
cin>>N;
vector<Server> all_sers; //存放所有的服务器参数
for(int i=0; i<N; i++)
{
string s;
cin>>s;
int pos;
vector<int> temp;
do
{
pos=s.find(',');
temp.push_back(stoi(s.substr(0, pos)));
s = s.substr(pos+1);
}while(pos != -1); //要记着这种将字符串转换为数组的方法
Server ser(temp[0], temp[1], temp[2], temp[3], temp[4]);
all_sers.push_back(ser);
}
//再读取最后一行的总要求
string s;
cin>>s;
int pos;
vector<int> temp;
do
{
pos=s.find(',');
temp.push_back(stoi(s.substr(0, pos)));
s = s.substr(pos+1);
}while(pos != -1); //要记着这种将字符串转换为数组的方法
int M = temp[0];
int stra = temp[1];
Server ser_need(-1, temp[2], temp[3], temp[4], temp[5]);
vector<int> results; //用于存放最后合适的结果
if(stra==1) //策略1：cpu优先，按照cpu从小到大排序
{
auto cmp = [](const Server &s1, const Server &s2) {
if(s1._n_cpu == s2._n_cpu && s1._n_mem == s2._n_mem) return s1._index < s2._index;
else return s1._n_cpu <s2._n_cpu;
};
sort(all_sers.begin(), all_sers.end(), cmp);
for(int i=0; i<all_sers.size(); i++)
{
if(all_sers[i]._n_cpu >= ser_need._n_cpu && all_sers[i]._n_mem >= ser_need._n_mem && (all_sers[i]._arch == ser_need._arch || all_sers[i]._arch == 9)
&& (all_sers[i]._np == ser_need._np || all_sers[i]._np == 2))
{
results.push_back(all_sers[i]._index);
}
if(results.size() == M) break;
}
}
else if(stra == 2)
{
auto cmp = [](const Server &s1, const Server &s2) {
if(s1._n_cpu == s2._n_cpu && s1._n_mem == s2._n_mem) return s1._index < s2._index;
return s1._n_mem < s2._n_mem;
};
sort(all_sers.begin(), all_sers.end(), cmp);
for(int i=0; i<all_sers.size(); i++)
{
if( all_sers[i]._n_cpu >= ser_need._n_cpu && all_sers[i]._n_mem >= ser_need._n_mem && (all_sers[i]._arch == ser_need._arch || all_sers[i]._arch == 9)
&& (all_sers[i]._np == ser_need._np || all_sers[i]._np == 2))
{
results.push_back(all_sers[i]._index);
}
if(results.size() == M) break;
}
}
cout<<results.size()<<' ';
for(auto &t:results)
{
cout<<t<<" ";
}
cout<<endl;
return 0;
}
/*
华为的机试题0728-2：
题目：大侠吃药
输入：
6
2
5
2 1
3 1
6 1
4 2
1 5
输出：
5
输入
第一行为要吃几幅药
第二行一天最多吃几幅
第三行输入接下来几组依赖关系
2 1表示吃了2才能吃1
3 1吃了3才能吃1
有依赖关系的不能一天吃
输出 最快4天吃完
思路：拓扑排序的方法,不过要注意同一天最多吃的次数。
*/
#include<bits/stdc++.h>
using namespace std;
int main()
{
int res=0; //总共要吃的天数
int n_total;
cin>>n_total;
int n_max;
cin>>n_max;
int m;
cin>>m;
vector<vector<int>> graph(n_total, vector<int>());
vector<int> indegrees(n_total, 0);
int a, b;
for(int i=0; i<m; i++)
{
cin>>a>>b;
graph[a-1].push_back(b-1);
indegrees[b-1]++;
}
queue<int> q;
for(int i=0; i<indegrees.size(); i++)
{
if (indegrees[i] == 0) q.push(i);
}
while(!q.empty())
{
//同一层，如果要吃的药大于每天能吃的最多的药，要吃多天
//这里是和leetcode课程表的题不一样的地方
int sz = q.size();
res += sz/n_max;
if((sz%n_max) != 0)
{
res++;
}
for(int i=0; i<sz; i++) //处理这一层
{
int cur = q.front();
q.pop();
for(auto &v:graph[cur])
{
indegrees[v]--;
if(indegrees[v] == 0)
{
q.push(v);
}
}
}
}
cout<<res<<endl;
return 0;
}
/*
华为的机试题0728-3：
题目：去西藏
3 4
1 0 0 0
0 0 0 0
0 0 2 -1
// 2
输入
二维矩阵 其中1表示起点，2表示终点，0可走，-1不可走
求从1开始经过所有0到2的路径数，不走重复节点
输出
有两条
*/
#include<bits/stdc++.h>
using namespace std;
int res = 0;
int n_zero=0;
void dfs(vector<vector<int>> &graph, int i, int j, int end_x, int end_y, int de_zero, vector<vector<bool>> visited)
{
if(i<0 || i>=graph.size() || j<0 || j>=graph[0].size() || graph[i][j] == -1 || visited[i][j])
{
return;
}
if(i == end_x && j==end_y)
{
// cout<<"de_zero="<<de_zero<<endl;
// cout<<"n_zero="<<n_zero<<endl;
if( de_zero == n_zero)
{
res++;
}
return;
}
visited[i][j] = true;
de_zero++;
dfs(graph, i+1, j, end_x, end_y, de_zero, visited);
dfs(graph, i-1, j, end_x, end_y, de_zero, visited);
dfs(graph, i, j+1, end_x, end_y, de_zero, visited);
dfs(graph, i, j-1, end_x, end_y, de_zero, visited);
visited[i][j] = false;
de_zero--;
}
int main()
{
int m, n;
cin>>m>>n;
vector<vector<int>> graph(m, vector<int>());
int a;
int start_x, start_y, end_x, end_y;
for(int i=0; i<m; i++)
{
for(int j=0; j<n; j++)
{
cin>>a;
if(a==1)
{
start_x = i;
start_y = j;
// cout<<"start_x="<<start_x<<";start_y="<<start_y<<endl;
}
if(a==2)
{
end_x = i;
end_y = j;
// cout<<"end_x="<<end_x<<";end_y="<<end_y<<endl;
}
else if(a==0)
{
n_zero++;
}
graph[i].push_back(a);
cout<<a<<' ';
}
cout<<endl;
}
vector<vector<bool>> visited(m, vector<bool>(n, false));
dfs(graph, start_x, start_y, end_x, end_y, -1, visited);
cout<<res<<endl;
return 0;
} 
