引言
打地鼠是一款考验反应速度与策略判断的经典街机游戏。地鼠随机从多个洞口冒出，玩家需要在有限时间内尽可能多地击中地鼠。当多个地鼠同时出现且时间窗口重叠时，如何规划击打顺序才能最大化得分？这正是区间调度问题的典型场景。本文将用Java实现一款带AI决策的打地鼠游戏，核心算法采用线段树（Segment Tree）维护区间覆盖信息，结合贪心策略求解最优击打序列。
问题建模
将打地鼠抽象为区间调度问题：
– 每个地鼠的冒出过程对应一个时间区间 [start, end]
– 每次击打消耗固定时间 hitDuration
– 若在某地鼠的存活区间内完成击打，则获得该地鼠的分数
– 目标：在总时间限制内，选择一组互不冲突（或允许有限重叠）的击打序列，使得总分最大
当击打间隔存在冷却时间或地鼠存在”连续出现奖励”时，我们需要在区间上快速查询最大得分，线段树便成为理想的数据结构。
核心算法：线段树区间最值与贪心调度
算法思路
- 区间离散化：将所有地鼠的
start和end时间戳离散化为整数坐标 - 动态规划状态设计：设
dp[i]表示处理完前i个时间单位能获得的最大分数 - 线段树优化转移：对于每个地鼠区间
[l, r]，更新dp[r] = max(dp[r], query_max(l, r) + score)，其中query_max用线段树在O(log n)内完成 - 贪心选择：按结束时间排序，优先处理先结束的地鼠（经典区间调度贪心）
复杂度分析
- 时间复杂度：
O(n log n)，其中n为地鼠数量，排序O(n log n)，每次线段树查询/更新O(log n) - 空间复杂度：
O(n)，用于存储线段树和离散化坐标
Java完整实现
import java.util.*;
/**
* 打地鼠游戏：线段树区间覆盖与最优击打调度
*
* 核心思路：
* 1. 将每只地鼠抽象为带权区间 [start, end, score]
* 2. 按结束时间排序，采用贪心+线段树DP求解最大得分
* 3. 线段树维护区间最大值，支持单点更新与区间查询
*/
public class WhackAMole {
// ============ 线段树类 ============
static class SegmentTree {
private int[] tree;
private int n;
public SegmentTree(int size) {
this.n = size;
this.tree = new int[4 * size];
}
/** 单点更新：将位置 pos 的值更新为 max(原值, val) */
public void update(int pos, int val) {
update(1, 0, n - 1, pos, val);
}
private void update(int node, int l, int r, int pos, int val) {
if (l == r) {
tree[node] = Math.max(tree[node], val);
return;
}
int mid = (l + r) >>> 1;
if (pos <= mid) {
update(node << 1, l, mid, pos, val);
} else {
update(node << 1 | 1, mid + 1, r, pos, val);
}
tree[node] = Math.max(tree[node << 1], tree[node << 1 | 1]);
}
/** 区间查询：查询 [ql, qr] 范围内的最大值 */
public int query(int ql, int qr) {
return query(1, 0, n - 1, ql, qr);
}
private int query(int node, int l, int r, int ql, int qr) {
if (ql > r || qr < l) {
return Integer.MIN_VALUE / 2; // 避免溢出
}
if (ql <= l && r <= qr) {
return tree[node];
}
int mid = (l + r) >>> 1;
return Math.max(
query(node << 1, l, mid, ql, qr),
query(node << 1 | 1, mid + 1, r, ql, qr)
);
}
}
// ============ 地鼠区间类 ============
static class MoleInterval implements Comparable<MoleInterval> {
int start; // 出现时间（毫秒或帧数）
int end; // 消失时间
int score; // 击中得分
int id; // 地鼠编号
public MoleInterval(int start, int end, int score, int id) {
this.start = start;
this.end = end;
this.score = score;
this.id = id;
}
@Override
public int compareTo(MoleInterval o) {
return Integer.compare(this.end, o.end); // 按结束时间升序
}
@Override
public String toString() {
return String.format("Mole[%d](%d~%d, score=%d)", id, start, end, score);
}
}
// ============ 游戏核心逻辑 ============
private List<MoleInterval> moles;
private int totalTime; // 游戏总时长
private int hitDuration; // 每次击打耗时
public WhackAMole(int totalTime, int hitDuration) {
this.moles = new ArrayList<>();
this.totalTime = totalTime;
this.hitDuration = hitDuration;
}
/** 添加一只地鼠 */
public void addMole(int start, int end, int score, int id) {
if (start >= 0 && end <= totalTime && start < end) {
moles.add(new MoleInterval(start, end, score, id));
}
}
/**
* 求解最优击打序列
* 算法：按结束时间排序后，使用线段树优化的动态规划
* dp[i] 表示在 sortedMoles[i].end 时刻之前能获得的最大分数
*/
public Result solveOptimalSchedule() {
if (moles.isEmpty()) {
return new Result(0, Collections.emptyList());
}
// 1. 按结束时间排序（贪心基础）
List<MoleInterval> sorted = new ArrayList<>(moles);
Collections.sort(sorted);
// 2. 坐标离散化：收集所有 start 和 end
Set<Integer> coordSet = new TreeSet<>();
for (MoleInterval m : sorted) {
coordSet.add(m.start);
coordSet.add(m.end);
}
List<Integer> coords = new ArrayList<>(coordSet);
Map<Integer, Integer> indexMap = new HashMap<>();
for (int i = 0; i < coords.size(); i++) {
indexMap.put(coords.get(i), i);
}
int m = coords.size();
// 3. 初始化线段树和DP数组
SegmentTree segTree = new SegmentTree(m);
int[] dp = new int[sorted.size()];
int[] prev = new int[sorted.size()]; // 记录前驱，用于回溯方案
Arrays.fill(prev, -1);
// dp[i] = max(不选i, 选i)
// 选i时：需要找到最后一个满足 end <= start_i 的区间j，dp[i] = dp[j] + score_i
// 用线段树维护以某个坐标结尾的最大dp值
int globalMax = 0;
int bestIdx = -1;
for (int i = 0; i < sorted.size(); i++) {
MoleInterval cur = sorted.get(i);
int si = indexMap.get(cur.start);
int ei = indexMap.get(cur.end);
// 查询在 cur.start 之前（含）的最大dp值
int bestBefore = segTree.query(0, si); // 允许击打时间刚好在start时刻开始
if (bestBefore < 0) bestBefore = 0;
dp[i] = bestBefore + cur.score;
// 同时考虑不选当前地鼠的情况（线段树已包含之前的最优值）
if (i > 0 && dp[i - 1] > dp[i]) {
// 这种情况在线段树查询中已经自然处理，因为不选i时不需要更新ei
}
// 记录前驱：找到使bestBefore最大的那个区间
// 简化处理：只记录当前选择的前驱为"最近的兼容区间"
for (int j = i - 1; j >= 0; j--) {
if (sorted.get(j).end <= cur.start) {
if (dp[j] + cur.score == dp[i]) {
prev[i] = j;
break;
}
}
}
if (prev[i] == -1 && bestBefore == 0) {
prev[i] = -1; // 无前驱，独立区间
}
// 更新线段树：在结束位置记录最大dp值
int currentMaxAtEnd = segTree.query(ei, ei);
if (dp[i] > currentMaxAtEnd) {
segTree.update(ei, dp[i]);
}
if (dp[i] > globalMax) {
globalMax = dp[i];
bestIdx = i;
}
}
// 4. 回溯最优序列
List<MoleInterval> schedule = new ArrayList<>();
int idx = bestIdx;
while (idx >= 0) {
schedule.add(sorted.get(idx));
idx = prev[idx];
}
Collections.reverse(schedule);
return new Result(globalMax, schedule);
}
/** 使用纯贪心策略（无线段树）作为对比 */
public Result solveGreedy() {
List<MoleInterval> sorted = new ArrayList<>(moles);
Collections.sort(sorted);
List<MoleInterval> schedule = new ArrayList<>();
int currentTime = 0;
int totalScore = 0;
for (MoleInterval m : sorted) {
if (m.start >= currentTime) {
schedule.add(m);
totalScore += m.score;
currentTime = m.end + hitDuration; // 击打后需要冷却
}
}
return new Result(totalScore, schedule);
}
// ============ 结果类 ============
static class Result {
int maxScore;
List<MoleInterval> schedule;
public Result(int maxScore, List<MoleInterval> schedule) {
this.maxScore = maxScore;
this.schedule = schedule;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("最大得分: ").append(maxScore).append("\n击打序列:\n");
for (MoleInterval m : schedule) {
sb.append(" ").append(m).append("\n");
}
return sb.toString();
}
}
// ============ 主程序：演示与测试 ============
public static void main(String[] args) {
// 场景：10秒游戏，每次击打耗时1秒
WhackAMole game = new WhackAMole(100, 10); // 时间单位：0.1秒
// 随机生成地鼠（实际游戏中由随机数生成器控制）
Random rand = new Random(42);
int moleCount = 20;
for (int i = 0; i < moleCount; i++) {
int start = rand.nextInt(80);
int duration = 5 + rand.nextInt(15); // 存活0.5~2秒
int end = Math.min(start + duration, 100);
int score = 10 + rand.nextInt(50);
game.addMole(start, end, score, i + 1);
}
System.out.println("=== 打地鼠：线段树最优调度 vs 纯贪心 ===\n");
Result optimal = game.solveOptimalSchedule();
System.out.println("【线段树DP最优解】");
System.out.println(optimal);
Result greedy = game.solveGreedy();
System.out.println("【纯贪心解】");
System.out.println(greedy);
int improvement = optimal.maxScore - greedy.maxScore;
double percent = greedy.maxScore > 0 ? (improvement * 100.0 / greedy.maxScore) : 0;
System.out.printf("\n优化提升: %d 分 (+%.1f%%)\n", improvement, percent);
}
}
关键代码解析
1. 线段树设计
线段树在本算法中承担两个职责：
– 区间最大值查询：快速获取在某个时间戳之前能获得的最大累积分数
– 单点更新：在区间结束位置记录当前最优DP值
相比普通数组的 O(n) 扫描，线段树将每次状态转移优化到 O(log n)，整体复杂度从 O(n²) 降至 O(n log n)。
2. 贪心与DP的结合
本算法首先按地鼠的结束时间升序排序，这是区间调度问题贪心的经典策略。排序后，每只地鼠只需考虑在它开始之前已经结束的地鼠，从而将二维冲突检测降为一维前缀查询，完美适配线段树的区间查询能力。
3. 前驱回溯
prev[] 数组记录每个最优状态的前一个地鼠索引，最终通过回溯链即可输出完整的击打序列，而非仅仅输出最大得分。
扩展思考
- 带权区间调度变体：若不同洞口的地鼠分值不同，上述算法天然支持，只需调整
score参数 - 多玩家竞争：引入博弈论框架，将地鼠视为公共资源，两名玩家的击打策略形成纳什均衡
- 实时增量更新：使用动态线段树或树状数组，可在游戏进行中实时插入新出现的地鼠并重新计算最优策略
总结
本文以打地鼠游戏为载体，展示了线段树在区间最值查询中的强大能力。通过将游戏过程抽象为带权区间调度问题，结合贪心排序与线段树优化的动态规划，我们在 O(n log n) 时间内求解出最优击打序列。该框架可扩展至会议室预订、任务调度、资源分配等广泛的实际应用场景。
