网易雷火笔试20240428
三小时四道题。游戏服务端工程师。
A: 100%
签到题。
模拟。
B: 82%
输入：n个任务，m天，n个任务的value和截止日期limit，m天中每天发放多少张券。一张券可以完成一个任务。
输出：最多能获得多少value。
贪心。
笔试后完善的代码：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(const pair<int, int> &a, const pair<int, int> &b) {
// 2. value相同时，日期大的排前面
// why? 获得一个相同的value，使用后面发的券更“优惠”（前面的券能cover的任务范围更大）
if (a.first == b.first)
return a.second < b.second;
// 1. value大的排前面
return a.first > b.first;
}
int main() {
int n, m; // m, n <= 1e6
cin >> n >> m;
vector<pair<int, int>> tasks;
for (int i = 0; i < n; ++i) {
int value, limit;
cin >> value >> limit;
tasks.push_back({value, limit});
}
sort(tasks.begin(), tasks.end(), cmp);
vector<int> tickets(m + 1);
for (int i = 1; i <= m; ++i) { // 第i天
cin >> tickets[i];
}
// 贪心算法，先把分数最高的任务（同分数以日期最高排序）和离截止日期最近的券匹配
long long ans = 0;
int start = 1; // start之前没有券了
for (int i = 0; i < tasks.size() && start <= m; ++i) {
int value = tasks[i].first, day = min(tasks[i].second, m);
// 极端情况下，每次都要遍历 m 次，这样就会超时。
// 考虑用map<天数，券数>存储tickets，删除券数为0的元素。
while (day >= start && tickets[day] == 0) --day;
if (day >= start) {
--tickets[day];
ans += value;
}
else
start = tasks[i].second + 1;
}
cout << ans << endl;
return 0;
}
/*
4 3
3 1
4 2
5 3
6 4
1
1
1
*/
C: 100%
PI和老虎要离开无人岛去漂流，出发前要准备食物和水。PI每天需要1份食物和2份水，老虎每天需要2份食物和1份水。船上的体积为x，食物n份，水m份，n + 3m <= x。PI和老虎都不能中断饮食，PI在断食后Q天死亡，老虎在断食后P天吃掉PI。
输入x、P、Q，输出PI最久能存活的天数。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int x, P, Q;
cin >> x >> P >> Q;
// pi吃一天需要1+3*2=7
// 老虎吃一天需要1*2+3=5
// 两者都吃一天需要12
long long ans = 0;
int diffDay = abs(P - Q), supply = 7;
if (P < Q)
supply = 5;
if (x < diffDay * supply)
ans = x / supply + min(P, Q);
else
ans = (x - diffDay * supply) / 12 + max(P, Q);
// if (P > Q) {
// if (x < (P - Q) * 7) {
// ans = x / 7 + Q;
// }
// else {
// x -= (P - Q) * 7;
// ans = x / 12 + P;
// }
// }
// else {
// if (x < (Q - P) * 5) {
// ans = x / 5 + P;
// }
// else {
// x -= (P - Q) * 5;
// ans = x / 12 + Q;
// }
// }
return 0;
}
D: 26%
n个量子台（每个量子台只能踏足一次），m个双向传送门（传送一次需要承受一定伤害w）。从 s 出发，到 e 取钥匙，然后到 t 回到现实世界。
如果能回到现实世界，输出最小的承受伤害；否则输出-1。
改善思路：最短路路径一定完整包含一条 s->e 最短，或者 e->t 最短（未证明）。实现时，分别找出 s->e（e->t）的最短路（可能不止一条），然后再找对应剩余图中的 e->t（e->s）的最短路，遍历这些组合。
不ac的代码（错误原因：只保存了到达某个点的最小距离，但最小不一定最好（路径不一样，对后续有影响），而且可能有多个最小）：
#include <iostream>
#include <tuple>
#include <queue>
#include <vector>
using namespace std;
int main() {
// 从 s 出发，到 e 取钥匙，然后到 t 回到现实世界
// 每个量子台只能踏足一次
int n, m, s, e, t;
cin >> n >> m >> s >> e >> t;
vector<vector<pair<int, int>>> edges(n + 1);
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w; // u,v ∈ [1, n]
edges[u].push_back({v, w});
edges[v].push_back({u, w});
}
// st[i]表示到达点i承受的（最小）伤害，-1表示还没到达
// st[i][0]未经过e st[i][1]经过e
vector<vector<long long>> st(n + 1, vector<long long>(2, -1));
queue<tuple<int, long long, vector<bool>>> q; // <当前到达的量子台，已承受的伤害，vis数组>
st[s][0] = 0;
vector<bool> vis(n + 1, false);
vis[s] = true;
q.push({s, 0, vis});
while (!q.empty()) {
auto tu = q.front(); q.pop();
int pos = get<0>(tu);
long long ww = get<1>(tu);
for (auto x : edges[pos]) {
vector<bool> v = get<2>(tu);
int nextPos = x.first;
if (v[nextPos]) continue;
v[nextPos] = true;
if (!v[e] && (st[nextPos][0] == -1 || ww + x.second < st[nextPos][0])) {
st[nextPos][0] = ww + x.second;
q.push({nextPos, st[nextPos][0], v});
}
if (v[e] && (st[nextPos][1] == -1 || ww + x.second < st[nextPos][1])) {
st[nextPos][1] = ww + x.second;
q.push({nextPos, st[nextPos][1], v});
}
}
}
cout << st[t][1] << endl;
return 0;
}
/*
5 7 1 4 5
1 2 5
1 3 1
4 2 6
5 4 14
3 4 2
1 5 6
5 3 3
*/
查看19道真题和解析