阿里巴巴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;
}
