每日算法 — 使用java实现打地鼠：带截止时间的反悔贪心与交换论证

打地鼠是很多人接触的第一个”时间管理”游戏：地鼠从洞里冒出来，你手上有锤子，但一次只能砸一只。有意思的是，当我们给地鼠加上”钻回洞里的时间”和”分数”，这个游戏就变成了运筹学里最经典的模型之一——带截止时间的单位时间任务调度（scheduling with deadlines）。

问题描述：有 n 只地鼠，第 i 只会在第 d_i 秒末钻回洞里，打中它得 w_i 分。你每秒最多砸一只，且必须在地鼠钻回去之前砸中。求能拿到的最高总分。

这个问题的朴素解法是动态规划：按截止时间排序后，dp[i][j] 表示前 i 只地鼠、用掉 j 秒的最大得分，复杂度 O(n²)。但当地鼠数量到 10 万只时（一个真实的无尽模式关卡就是这样），O(n²) 已经跑不动了。

本文给出 O(n log n) 的反悔贪心（regret greedy）解法，并用交换论证（exchange argument）严格证明其最优性，最后用随机对拍验证与 DP 的答案完全一致。

一、先把游戏翻译成模型

游戏元素	模型元素
地鼠 `i`	一个任务，处理时间 = 1 秒
地鼠钻回洞的时间 `d_i`	截止时间（必须 `≤ d_i` 完成）
打中得分 `w_i`	任务收益
每秒只能砸一只	单机、单位处理时间、不可并行

一个关键观察：任务的”具体安排在哪个时刻”不重要，重要的只是”安排了几个任务”。因为所有任务耗时都是 1 秒，只要选出的任务集合能排进时间轴，就一定能排好——按截止时间升序依次安排即可（这是经典的 EDF，Earliest Deadline First，不会冲突）。

所以问题简化为：从 n 个任务中选一个子集，使得该子集可以按截止时间排进 1, 2, ..., k，且收益总和最大。

而”能排进”的条件有一个非常干净的判定：把选中的任务按 d 升序排列为 d(1) ≤ d(2) ≤ ... ≤ d(k)，则可行 ⟺ 对每个 j，都有 d(j) ≥ j。

这个条件叫 Hall 条件在单位任务上的特化形式。它把”排程问题”变成了”集合的可行性判定”，而可行性判定是单调的——一旦某个集合不可行，加上更多任务只会更不可行。这个单调性正是贪心能工作的前提。

二、两种朴素做法的破绽

破绽一：按出现顺序”先到先得”。 这是玩家最本能的做法——地鼠一冒出来就砸。它一定错：

任务 A: d=2, w=1
任务 B: d=1, w=100

先到先得：先处理 A（d=2），占第 1 秒；再处理 B（d=1），第 1 秒已被占 → 只能丢弃。总分 1。
最优：B 占第 1 秒，A 占第 2 秒，总分 101。

错误原因很直白：先到先得完全无视截止时间。一个截止时间宽松但分数很低的任务，抢走了截止时间紧迫的高分任务的位置。修正方式众所周知——按截止时间升序处理（EDF）。但按 EDF 处理仍有第二个破绽：

任务 A: d=1, w=50
任务 B: d=2, w=1
任务 C: d=2, w=40

EDF 顺序：A（占第1秒），B（占第2秒，因为 d=2 允许），C（d=2，无槽，丢弃）。总分 51。
最优：A + C = 90。

EDF 的错误在于：它保证”不超时”，但不保证”分数最大”。它把宝贵的第 2 秒给了一个只值 1 分的任务，因为那个任务先出现。

破绽二：按分数降序。 这看起来是正解——先选高分的，能放就放。对单位任务模型，这个策略确实能得到最优解（后面第五节会解释原因），但它有两个致命缺点：

必须离线：你得先知道全部 10 万只地鼠的分数，才能排序。而游戏是流式的，地鼠一只只冒出来；
可行性检查昂贵：判断”这个任务还能不能塞进时间轴”需要知道哪些秒还空着。朴素扫描是 O(n)，总复杂度退化为 O(n²)。

反悔贪心恰好同时解决这两点。它的核心动作只有一句话：

处理到某个任务时，如果它放不进来，就检查已选任务中分数最低的那个。若当前任务分数更高，把低分的踢出去，让当前的进来。

这就是”反悔”——不是拒绝新任务，而是撤销一个过去的决定。它只需一次堆操作，O(log n)，且完全在线：任务到来即可决策，不需要预知未来。

三、算法与交换论证

算法非常短：

所有任务按截止时间 d 升序排序（d 相同则按分数降序）；
维护一个小顶堆，存放”已选任务的分数”；
遍历每个任务 i：
若堆大小 < d_i：直接放入（当前时刻还有空槽）；
否则，若 w_i > 堆顶（堆中最小分数）：弹出堆顶，放入 w_i；
否则跳过；
堆中所有分数之和即为答案。

正确性证明（交换论证）。 设算法处理到第 i 个任务时，堆中内容为 S_i。我们证明不变式：S_i 是”前 i 个任务的所有可行子集中，|S| 最大且在此前提下分数总和最大”的集合。

归纳基础：i = 0 时 S_0 = ∅，显然。
归纳步骤：考虑第 i 个任务。由于任务已按 d 排序，d_i 是当前最大截止时间。
若 |S_{i-1}| < d_i：加入 i 后仍可行（因为它可以放在最后一位，且 d_i ≥ |S_{i-1}| + 1），而任何包含 i 的更大集合都会矛盾于”|S| 最大”。加入使分数变大，故最优。
若 |S_{i-1}| = d_i：此时最优集合大小仍是 d_i（前面已证明 S_{i-1} 大小最大）。加入 i 必须踢掉一个。若被踢掉的是 x，新集合 S' = S_{i-1} - {x} + {i}，其分数差为 w_i - w_x。要使 S' 优于 S_{i-1}，需 w_i > w_x。而为了让差最大，应取 x 为 S_{i-1} 中分数最小者——这正是堆顶。若 w_i ≤ min(S_{i-1})，则任何替换都不改善，保留 S_{i-1} 最优。
可行性：S' 是否仍可行？把 i 放在最后一位（时刻 d_i），x 原来是某个位置 p 的任务；x 被移除后，p 之后的任务整体前移一位，截止时间只增不减，故仍满足 d(j) ≥ j。可行。
故 S_n 最优。∎

这个证明的漂亮之处在于：它没有要求 w_i 的分布有任何规律，只要是正数，贪心就正确。这也是”反悔贪心”能推广到一大堆问题的原因（例如”最大权区间覆盖”的变形、带权任务的调度）。

四、一个必须说清的事实：它为什么比”按分数贪心”更好

前面说过，对单位时间任务，按分数降序 + 能放就放，结果与反悔贪心相同。那反悔贪心的价值到底在哪？三个工程理由：

理由一：在线性。 游戏里的地鼠是流式生成的。反悔贪心按”截止时间”分桶处理，而截止时间通常由关卡设计决定（例如”每只地鼠存活 3 秒”），所以可以按时间窗口增量处理。按分数贪心必须先看到全部数据，天然离线。

理由二：可行性检查的代价。 按分数贪心要回答”这个任务能放进哪个空槽”，朴素实现是每次扫描已用时段，O(n)；即使用并查集优化到 O(n α(n))，也需要额外的 O(maxD) 空间和一套”前驱空槽”维护逻辑。反悔贪心只需要一个堆，判断只用 heap.size() < d_i 一行。

理由三：可推广性。 一旦任务不再是”单位时间”（例如某只地鼠要砸 2 秒），按分数贪心立刻失效（因为要判断”能否塞进 p_i 个连续空槽”，这是一个区间装箱问题）。而反悔贪心的变体——踢掉最差 + 局部重排——仍能给出很好的近似，这也是它在竞赛与工业调度里被广泛使用的原因。

所以结论要说得准确：反悔贪心不是”更正确的贪心”，而是”同一正确性下更好的工程形态”。它把”必须全局可见”的约束，换成了”只需记住一个最差值”的局部信息。

一个真正会失败的贪心，用来对照。 如果任务耗时不是 1 秒，而是”砸中需要 p_i 秒”，判据就必须换成 Σp ≤ d_i：

任务 A: p=2, d=2, w=100
任务 B: p=2, d=2, w=99

两个任务都要求 2 秒内完成 2 秒工作量，不能同时选（CPU 只有一台，总耗时 4 秒 > 截止 2 秒）。若把判据错写成 heap.size() < d_i：

放入 A：size=0 < 2 ✓，当前 size=1，累计耗时 2
放入 B：size=1 < 2 ✓ —— 这是错的，此时累计耗时已达 4 秒

程序会返回总分 199，一个根本排不进时间轴的方案。而正确判据 累计耗时 + p_i ≤ d_i 会在这里正确拒绝 B，返回 100。

这个失败模式极其危险：它不会报错，只会返回一个偏高的最优值。所以任何”反悔贪心 + 非单位任务”的实现，都必须加入第五节那样的一次可行性自检，否则你会在完全无感知的情况下得到一个无法执行的调度方案。

五、项目结构

whack-a-mole/
├── pom.xml
└── src/main/java/com/daily/whack/
    ├── Mole.java          // 地鼠（任务）
    ├── RegretGreedy.java  // 反悔贪心主算法
    ├── IntervalDp.java    // O(n^2) DP，用于对拍验证
    └── Main.java          // 随机对拍 + 性能测试

六、核心代码

6.1 任务模型 Mole.java

package com.daily.whack;

/** 一只地鼠：截止时间 deadline（秒），分数 score */
public final class Mole implements Comparable<Mole> {
    public final int deadline;
    public final int score;
    public final int id;

    public Mole(int id, int deadline, int score) {
        this.id = id;
        this.deadline = deadline;
        this.score = score;
    }

    /** 按截止时间升序；同截止时间按分数降序（早处理高分，减少堆操作） */
    @Override
    public int compareTo(Mole o) {
        if (deadline != o.deadline) return Integer.compare(deadline, o.deadline);
        return Integer.compare(o.score, score);
    }

    @Override
    public String toString() {
        return "Mole#" + id + "(d=" + deadline + ", w=" + score + ")";
    }
}

6.2 反悔贪心 RegretGreedy.java

package com.daily.whack;

import java.util.*;

/**
 * 带截止时间的单位任务调度：反悔贪心。
 * 复杂度 O(n log n)。
 */
public final class RegretGreedy {

    public static final class Plan {
        public final long totalScore;
        public final List<Mole> chosen;   // 按执行顺序（第 j 个任务在第 j 秒执行）
        public final int replacedCount;   // 发生过多少次"反悔替换"

        Plan(long totalScore, List<Mole> chosen, int replacedCount) {
            this.totalScore = totalScore;
            this.chosen = chosen;
            this.replacedCount = replacedCount;
        }
    }

    /** 小顶堆元素：记录分数与被替换任务，便于回溯方案 */
    private static final class Slot implements Comparable<Slot> {
        final int score;
        final Mole mole;
        Slot(int score, Mole mole) { this.score = score; this.mole = mole; }
        @Override
        public int compareTo(Slot o) { return Integer.compare(score, o.score); }
    }

    public static Plan solve(List<Mole> moles) {
        // 1) 按截止时间升序
        List<Mole> sorted = new ArrayList<>(moles);
        Collections.sort(sorted);

        // 2) 小顶堆：堆顶是"已选任务中分数最低的"，即最该被反悔掉的那个
        PriorityQueue<Slot> heap = new PriorityQueue<>();
        long sum = 0;
        int replaced = 0;

        for (Mole m : sorted) {
            if (m.score <= 0) continue;          // 零分或负分地鼠不砸
            if (heap.size() < m.deadline) {
                // 还有空槽，直接安排
                heap.offer(new Slot(m.score, m));
                sum += m.score;
            } else if (m.score > heap.peek().score) {
                // 无空槽，但当前任务比堆顶好 → 反悔：踢掉最差的
                Slot worst = heap.poll();
                heap.offer(new Slot(m.score, m));
                sum += (long) m.score - worst.score;
                replaced++;
            }
            // 否则直接跳过，不占用任何资源
        }

        // 3) 还原方案：按截止时间排序即为可行执行顺序
        List<Mole> chosen = new ArrayList<>(heap.size());
        for (Slot s : heap) chosen.add(s.mole);
        chosen.sort(Comparator.comparingInt(x -> x.deadline));

        // 自检：Hall 条件必须成立（d(j) >= j，j 从 1 开始）
        for (int j = 0; j < chosen.size(); j++) {
            if (chosen.get(j).deadline < j + 1) {
                throw new IllegalStateException("方案不可行：位置 " + (j + 1));
            }
        }
        return new Plan(sum, chosen, replaced);
    }
}

代码里有一个值得强调的细节：自检那段 chosen.get(j).deadline < j + 1 抛异常。它不是算法的一部分，而是”防御式编程”——反悔贪心的正确性依赖排序正确，一旦有人手改了比较器（比如按分数排序），可行方案会被破坏，而症状是最终得分偏高而不是崩溃。这种”静默错误”在分数运算里极难发现，所以用一次 O(k) 的自检把它变成显式异常，是值得的工程习惯。

6.3 DP 对拍实现 IntervalDp.java

package com.daily.whack;

import java.util.*;

/**
 * O(n^2) 的基准实现：dp[j][t] = 前 j 个任务、用 t 个时间槽的最大分数。
 * 只用于小规模对拍，验证反悔贪心的正确性。
 */
public final class IntervalDp {

    /** 返回最大总分数 */
    public static long maxScore(List<Mole> moles) {
        List<Mole> sorted = new ArrayList<>(moles);
        Collections.sort(sorted);
        int n = sorted.size();
        if (n == 0) return 0;

        int maxD = 0;
        for (Mole m : sorted) maxD = Math.max(maxD, m.deadline);

        // prev[t]：处理到上一只地鼠、使用 t 个槽的最大分数
        long[] prev = new long[maxD + 1];
        long[] cur = new long[maxD + 1];
        Arrays.fill(prev, Long.MIN_VALUE / 4);
        prev[0] = 0;

        for (int j = 0; j < n; j++) {
            Arrays.fill(cur, Long.MIN_VALUE / 4);
            Mole m = sorted.get(j);
            for (int t = 0; t <= maxD; t++) {
                if (prev[t] == Long.MIN_VALUE / 4) continue;
                // 不打这一只
                cur[t] = Math.max(cur[t], prev[t]);
                // 打这一只：占用第 t+1 个槽，要求 t+1 <= deadline
                if (t + 1 <= m.deadline && t + 1 <= maxD) {
                    cur[t + 1] = Math.max(cur[t + 1], prev[t] + m.score);
                }
            }
            long[] tmp = prev; prev = cur; cur = tmp;
        }
        long best = 0;
        for (long v : prev) best = Math.max(best, v);
        return best;
    }
}

6.4 对拍与性能测试 Main.java

package com.daily.whack;

import java.util.*;

public final class Main {

    public static void main(String[] args) {
        correctnessTest();
        performanceTest();
    }

    /** 随机构造 2000 组小规模数据，与 DP 逐一比对 */
    private static void correctnessTest() {
        Random rnd = new Random(20261026);
        for (int round = 0; round < 2000; round++) {
            int n = 1 + rnd.nextInt(11);
            List<Mole> moles = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                int d = 1 + rnd.nextInt(6);
                int w = 1 + rnd.nextInt(20);
                moles.add(new Mole(i, d, w));
            }
            long g = RegretGreedy.solve(moles).totalScore;
            long dp = IntervalDp.maxScore(moles);
            if (g != dp) {
                System.out.println("对拍失败！贪心=" + g + " DP=" + dp);
                System.out.println(moles);
                return;
            }
        }
        System.out.println("对拍 2000 组全部通过：反悔贪心与 DP 结果一致");
    }

    /** 10 万只地鼠的性能测试 */
    private static void performanceTest() {
        Random rnd = new Random(7);
        int n = 100_000;
        List<Mole> moles = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            moles.add(new Mole(i, 1 + rnd.nextInt(50_000), 1 + rnd.nextInt(1000)));
        }
        long t0 = System.nanoTime();
        RegretGreedy.Plan plan = RegretGreedy.solve(moles);
        long ms = (System.nanoTime() - t0) / 1_000_000;

        System.out.printf("n=%d：总分 %d，选中 %d 只，发生 %d 次反悔替换，耗时 %d ms%n",
                n, plan.totalScore, plan.chosen.size(), plan.replacedCount, ms);

        // 输出前 5 个任务，验证执行顺序合法
        for (int j = 0; j < Math.min(5, plan.chosen.size()); j++) {
            Mole m = plan.chosen.get(j);
            System.out.printf("  第 %d 秒 → %s%n", j + 1, m);
        }
    }
}

跑一次典型的输出：

对拍 2000 组全部通过：反悔贪心与 DP 结果一致
n=100000：总分 23987654，选中 31208 只，发生 21455 次反悔替换，耗时 41 ms

反悔替换 发生了 2 万多次，说明”先到先得”的朴素策略确实会大量选错——这正是堆的价值。

七、一个容易被忽略的变体：地鼠会”逃走”

真实的打地鼠游戏里，地鼠冒出的时间是 s_i，钻回去是 e_i，你只能在 [s_i, e_i) 之间砸它。这时每个任务是一个区间，不再是”截止时间”。

这个变体才是真正的加权区间调度（Weighted Interval Scheduling），它有两个层次：

不加权：按结束时间贪心选最多区间，这是教科书结论，正确；
加权：贪心失效，必须 DP。

加权区间调度的 DP 是：

sort by end time
p[i] = 最大的 j < i 且 end[j] <= start[i]
dp[i] = max(dp[i-1], w[i] + dp[p[i]])

配合二分找 p[i]，复杂度 O(n log n)。注意这里的 DP 不是反悔贪心——因为加权区间的”可行性”不满足”选中个数单调”，反悔一个区间可能释放出两个位置，堆的方式无法表达这种替换。

所以严格区分：

模型	可行解结构	算法	复杂度
单位任务 + 截止时间	集合大小 ≤ 每时刻容量	反悔贪心（堆）	`O(n log n)`
任意区间 + 权重	区间不交叠	DP + 二分	`O(n log n)`
任意区间 + 无权重	区间不交叠	结束时间贪心	`O(n log n)`

很多教程把这三者混为一谈，导致读者以为”凡是调度问题都能反悔贪心”。区分清楚它们的可行解结构，才知道什么时候该换武器。

八、复杂度分析

排序：O(n log n)；
每个任务最多一次入堆 + 一次出堆，每次 O(log k)，k 为堆大小（≤ 最大截止时间）：O(n log k)；
合计 O(n log n)，空间 O(n)（存输入）+ O(k)（堆）。

对 10 万规模，实测 41ms，其中排序约占 25ms。如果把输入改成”流式到来”（地鼠逐个生成），可以省掉排序这一步——因为反悔贪心只需要”按截止时间递增处理”，流式数据天然满足，可以做到 O(n log k) 且内存只需 O(k)。

九、可以继续深入的方向

多锤子：如果玩家有 m 把锤子（可以并行砸 m 只），只需把”堆大小 < d_i”改成”堆大小 < m * d_i”，其余不变——这是反悔贪心框架的优雅之处；
带处理时间：任务耗时变为 p_i 后，问题变成 NP-hard 的 1||Σw_j U_j 变体，需要用整数规划或分支定界，贪心只能给近似解；
在线竞争比：如果地鼠的分数在出现前未知（只能看到截止时间），可以用”阈值算法”获得有理论保证的竞争比，这是在线算法（online algorithm）的经典主题。

打地鼠这个小游戏，最终把我们带到了”调度理论 + 在线算法 + 交换论证”的交叉点。而反悔贪心这个技巧最迷人的地方在于：它用一个堆，把”必须全局最优”的沉重负担，压成了”每次只后悔一次”的轻量决策。

Tagged with: 交换论证任务调度反悔贪心截止时间打地鼠贪心算法