2026/4/25 网易互娱笔试题
T1：贪心
题目描述：模拟打怪兽游戏，一共有n个怪物，玩家的初始护盾时间为x，每秒造成伤害为y。
- 每次攻击怪物时，如果怪物血量为h，则用时为$\lceil \frac{h}{y} \rceil$，当前护盾时间为s：若 s < $\lceil \frac{h}{y} \rceil$，则立刻结束，不会触发后续操作；否则，玩家击杀怪物，护盾时间增加x，即s = s - $\lceil \frac{h}{y} \rceil$ + x。
- 怪物死前血量为h，则死后以2倍h的血量复活。因此怪物数量永远不会变。
- 玩家能自主选择要打哪个怪物。当游戏结束时，打印总时间，即玩家击杀的所有怪物耗时加剩余的护盾时间s。
输入：第一行输入n，x，y，第二行输入n个数表示怪物初始血量。
思路：这题就是贪心算法，每次都选择当前血量最少的怪物打。实现上可以用优先队列实现。
伪代码：
priority_queue<int, vector<int>, greater<int>> pq; // 最小堆
int s = x; // 初始护盾时间
int ret = 0; // 返回总时间
while(true){int h = pq.top();int time = h / y 上取整;if (s < time){break; // 直接结束} else{s = s - time + x;ret += s;pq.pop();pq.push(2*h); // 怪物以两倍血量复活}
}
ret += s;
通过率：35%，不知道为啥
T2：最短路径
题目描述：在太空中开飞船，地图上有障碍物，目标是从S到T，操作：
- 加速：一单位时间，花费一燃料，速度加一，先改变速度再移动，最大速度是3
- 减速：一单位时间，花费一燃料，速度减一，先移动再改变速度
- 匀速：一单位时间，不划分燃料，匀速直线运动
- 转向：飞船只有在静止时才能转向，转向不消耗时间和燃料。
求从S到T，且飞船必须在T静止，花费的最短时间和燃料，若时间相同，则选燃料更小的。
输入：第一行输入R，C，表示R行C列，第二行输入网格，类似：
..S..
.....
###..
.....
..T..
思路：我的理解是，由于只能在静止时转向，所以考虑直线运动的代价，若当前坐标为p，目标坐标与p的距离为d：
- d = 1， 路径非法，因为加速减速走的距离至少是2
- 2 <= d < 6，速度最大为1，加速减速花费时间为2，燃料为2，匀速花费时间为x，d = 2 + x；
- 6 <= d < 12，速度最大为2，加速减速花费时间为6，燃料为4，v=1匀速时间为x，v=2匀速时间为y，d = 6 + x + y；
- 12 <= d，速度最大为3，加速减速花费时间为12，燃料为6，d = 12 +x + y + z。
在dijkstra算法中，令与当前点相邻的点是横竖两条直线上的点，在网格范围内且没有障碍阻挡。
伪代码：
priority_queue pq; // 获取当前时间最小的点
pq.push({S, 0, 0});
while(!pq.empty()){P top = pq.top(); pq.pop();遍历点top四个方向上的合法点q：计算top到q的时间和燃料;if (q的时间有所更新){更新时间和代价pq.push(...);}
}
输出T的时间和燃料。
通过率：30%，也不知道为啥