华为七月份机试题总结4-0728

/*
华为的机试题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;
}