华为机试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;
}

#华为机试##笔试题目##面经#