阿里巴巴8.23笔试(AC100%)

1. 三人打牌，每个人都有n张排，每次每个人都出一张牌，留下最小的一张，n次操作之后，最小的牌的和最小是多少

解法：贪心+队列模拟。各自排序后，每次从队列头取最小值，其他人就取最大值。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 100;
int a[3][N];
int main()
{
    int n;
    while (~scanf("%d", &n))
    {
        deque<int> q[3];
        for (int i = 0; i < 3; i++)
        {
            for (int j = 0; j < n; j++)
            {
                scanf("%d", &a[i][j]);
            }
            sort(a[i], a[i]+n);
            for(int j = 0; j < n; j++ ) q[i].push_back(a[i][j]);
//            for (int j = 0; j < n; ++ j) cout << a[i][j] << ' ';
//            cout << '\n';
        }

        using ll = long long;
        ll ans = 0;
        for (int i = 0; i < n; i++)
        {
            int x = q[0].front();
            int y = q[1].front();
            int z = q[2].front();
            //printf("x = %d, y = %d, z = %d\n", x, y, z);
            if (x <= y && x <= z)
            {
                ans += x;
                q[0].pop_front();
                q[1].pop_back();
                q[2].pop_back();
            }
            else if (y <= x && y <= z)
            {
                ans += y;
                q[1].pop_front();
                q[0].pop_back();
                q[2].pop_back();
            }
            else {
                ans += z;
                q[2].pop_front();
                q[0].pop_back();
                q[1].pop_back();
            }
        }

        printf("%lld\n", ans);



    }
    return 0;
}

2，给出一个图，初始自己有p升油，图上的每个点都有水量，问选择哪一个点作为核心点，然后用车把其他点的水运来，最终要是得核心点得水尽可能多i。

解法：最短路+01背包，使用Floyd计算出最短路，01背包计算方案

#include <bits/stdc++.h>
using namespace std;

const int N = 502 + 100;
const int inf = 0x3f3f3f3f;

int a[N][N], dist[N][N];
long long w[N];
int n,m,p;
long long dp[N][N];

int main()
{

    while (~scanf("%d%d%d", &n, &m, &p))
    {
        memset(a, 0x3f, sizeof a);
        for (int i = 0; i <= n; i++) a[i][i] = 0;

        for (int i = 1; i <= n; ++ i) scanf("%lld", &w[i]);
        for (int i = 1; i <= m; ++ i)
        {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            a[x][y] = a[y][x] = min(a[x][y], z << 1);
        }


        for (int k = 1; k <= n; ++ k)
            for (int i = 1; i <= n; ++ i)
                for (int j = 1; j <= n; ++ j)
                {
                    a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
                }

//        for (int i = 1; i <= n; ++ i )
//        {
//            for (int j = 1; j <= n;  ++ j)
//            {
//                printf("a[%d][%d] = %d\n", i, j, a[i][j]);
//            }
//            puts("");
//        }


        long long ans = 0;
        int index = -1;
        for (int i = 1; i <= n; ++ i)
        {
            memset(dp, 0, sizeof dp);
            for (int j = 1; j <= n; ++ j)
            {
                for (int k = p; k >= a[i][j]; -- k)
                {
                    dp[i][k] = max(dp[i][k], dp[i][k - a[i][j]] + w[j]);
                }
            }
            if (ans < dp[i][p]) ans = dp[i][p], index = i;
        }

        printf("%d %lld\n", index, ans);

    }
    return 0;
}

#阿里巴巴笔试##阿里巴巴##笔经#