华为机试4月17
第一第二道过了百分之百，第三道百分之95。
第三道可能是我没有用状态压缩，提前交卷了。
第一题排序
输入 h , m
h表示小明的身高
m 表示下一行有 m 个人的身高
要求输出与小明身高差最小的，按照从小到大排序。
思路：
用哈希表记录当前身高差和与小明身高差的绝对值，然后按照从小到大排序，身高差相同则按照先后顺序
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
int main(){
int h,n;
cin >> h >> n;
vector<int> nums(n);
vector<pair<int,int> > res;
for(int i = 0; i < n; i++){
cin >> nums[i];
res.push_back(make_pair(nums[i], abs(h - nums[i])));
}
sort(res.begin(), res.end(), [](const pair<int,int>& a, const pair<int,int>& b){
if(a.second == b.second) return a.first < b.first;
return a.second < b.second;
});
for(int i = 0; i < n; i++){
if(i == n - 1){
cout << res[i].first << endl;
}
else cout << res[i].first << " ";
}
return 0;
} 第二题，判断是不是在一个队
输入 n ,m
n 表示从 1-n,
m表示后面有 m 行
a b c
a,b要在（1，n)内
c = 0 表示在一个队内，输出we are a team，
c = 1 表示需要判断
c = 其他则输出da pian zi
如果不在一个队就输出we are not a team
思路：
标准的并查集
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
const int N = 1e5 + 10;
int n,m;
vector<int> fa;
void init(int len){
fa.resize(len);
for(int i = 0; i < len; i++){
fa[i] = i;
}
}
int find(int x){
if(x != fa[x]){
fa[x] = find(fa[x]);
}
return fa[x];
}
void merge(int x, int y){
x = find(x);
y = find(y);
fa[x] = y;
}
int main(){
cin >> n >> m;
if(n < 1 || n > 100000 || m < 1 || m > 100000){
cout << "NULL\n";
return 0;
}
init(n);
for(int i = 0; i < m; i++){
int x, y, p;
cin >> x >> y >> p;
if(x < 1 || x > n || y < 1 || y > n){
cout << "da pian zi\n";
}else{
if(p == 0){
merge(x, y);
}
else if(p == 1){
if(find(x) == find(y)){
cout << "we are a team\n";
}else{
cout << "we are not a team\n";
}
}else{
cout << "da pian zi\n";
}
}
}
return 0;
}
第三题： 组成一面墙的最小层数
墙只能由高和宽相对堆叠。
输入：给定一组数据，用空格分开（应该是宽度，记不清了）
例如：
3 6 3 3 3
输出 3，
解释：以 6 为底的墙，第一层为 6 ，第二层为 3 + 3 第三层 3 + 3
思路：
一开始看到有点懵，后面一想不就是背包问题吗，先计算和sum，排序，我们选取最大的maxVal作为墙的第一层
如果 sum % maxVal == 0，代表可以这样划分，如果不可以则 maxVal += maxVal + nuns[i], 加上最小的。
可以化分的层数就为 cnt = sum / maxVal
背包容量就为：sum /= cnt;
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
void Stringsplit(string str, const char split, vector<int>& res){
istringstream iss(str);
string tmp;
while(getline(iss, tmp, split)){
res.push_back(stoi(tmp));
}
}
int main(){
string str;
vector<int> nums;
getline(cin,str);
Stringsplit(str, ' ', nums);
int n = nums.size();
if(n == 1){
cout << 1 << endl;
return 0;
}
if(n == 0){
cout << -1 << endl;
return 0;
}
sort(nums.begin(), nums.end());
int maxVal = nums[n - 1];
int sum = 0;
for(int i = 0; i < n; i++){
sum += nums[i];
}
for(int i = 0; i < n - 1; i++){
if(sum % maxVal == 0){
break;
}else{
maxVal += nums[i];
}
}
int cnt = sum / maxVal;
sum /= cnt;
vector<vector<bool> > dp(n + 1, vector<bool>(sum + 1, false));
//base case
for(int i = 0; i <= n; i++){
dp[i][0] = true;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= sum; j++){
if(j - nums[i - 1] < 0){
dp[i][j] = dp[i - 1][j];
}else{
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
}
}
}
if(dp[n][sum] == true){
cout << cnt << endl;
}else{
cout << -1 << endl;
}
return 0;
} 
