得物笔试8.23

算法工程师（工程方向）

第一题：给定n<1e3个数字，每个数字 x<1e5，数字会有重复，给定m<1e5，从中选k个数字，它们的和等于m，求k的最小值。

应该是01背包，但是当时想着O(n*m)=1e8就没用，所以最后是dfs剪枝，一开始没加flag，只能过80，加了之后就a了，但是我感觉加了会有问题。

#include <bits/stdc++.h>
using namespace std;
int n, m, ans, tot = 0, flag = 0;
int a[1005], b[1005];
void dfs(int pos, int num, int sum)
{
    if (sum == m)
    {
        ans = min(ans, num);
        flag = 1;
        return;
    }
    while (pos >= 0 && a[pos] + sum > m)
        pos--;
    for (int i = pos; i >= 0; --i)
    {
        if (b[i] + sum < m)
            return;
        if (b[i] + sum == m)
        {
            ans = min(ans, num + i + 1);
            flag = 1;
            return;
        }
        if (a[i] + sum == m)
        {
            ans = min(ans, num + 1);
            flag = 1;
            return;
        }
        dfs(i - 1, num + 1, sum + a[i]);
        if (flag)
            return;
    }
}
int main()
{
    cin >> n >> m;
    ans = n + 1;
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &a[i]);
        tot += a[i];
    }
    if (tot < m)
    {
        cout << "No solution";
        return 0;
    }
    if (tot == m)
    {
        cout << n;
        return 0;
    }
    sort(a, a + n);
    b[0] = a[0];
    for (int i = 1; i < n; ++i)
        b[i] = b[i - 1] + a[i];
    for (int i = n - 1; i >= 0; --i)
    {
        if (a[i] > m)
            continue;
        if (a[i] == m)
        {
            cout << 1;
            return 0;
        }
        dfs(i, 0, 0);
    }

    if (ans == n + 1)
        cout << "No solution";
    else
        cout << ans;
    system("pause");
    return 0;
}
/*
4 23
8 9 2 13
*/

第二题：最小生成树，模板题

#include <bits/stdc++.h>
using namespace std;
#define LL long long
struct node
{
    node() {}
    node(int a, int b, int c)
    {
        u = a, v = b, w = c;
    }
    bool operator<(const node &x) const
    {
        return w < x.w;
    }
    int u, v, w;
};
int n, m, u, v, w, f[105];
priority_queue<node> pq;
LL ans = 0;
int find(int x)
{
    if (x == f[x])
        return x;
    return f[x] = find(f[x]);
}
int main()
{
    cin >> n >> m;
    while (m--)
    {
        scanf("%d%d%d", &u, &v, &w);
        pq.emplace(u, v, w);
    }
    for (int i = 1; i <= n; ++i)
        f[i] = i;
    while (!pq.empty())
    {
        auto cur = pq.top();
        pq.pop();
        int fu = find(cur.u), fv = find(cur.v);
        if (fu == fv)
            continue;
        f[fu] = f[fv];
        ans += cur.w;
    }
    int rt = find(1);
    for (int i = 2; i <= n; ++i)
    {
        if (find(i) != rt)
        {
            cout << "No solution";
            return 0;
        }
    }
    cout << ans;
    system("pause");
    return 0;
}

/*
3 3
1 2 10
1 3 20
2 3 30

4 5
1 2 5
1 3 6
1 4 7
2 4 1
3 4 8
*/