1. 从“几何”到“反悔贪心”这两个标签到底在说什么如果你经常刷算法题肯定见过那种一眼看去像是“计算几何”的题目结果最后正解却是贪心加堆也见过表面上是贪心题实际却暗藏了凸包、曼哈顿距离转切比雪夫距离这种几何变换。标题里的“几何|反悔贪心pq”其实是一类很典型的组合标签——它意味着这道题的题解大概率是“贪心策略 优先队列priority queue简称pq实现反悔操作”而“几何”则指明了题目的背景或关键性质。先说结论这类题的核心套路通常就一句话——先凭直觉定一个贪心顺序再用堆来支持“反悔”。至于几何背景可能是用来约束排序规则也可能是用来简化决策的单调性还可能纯粹是诱导你往复杂算法上想。我见过太多人在“几何”这个标签上栽跟头一上来就写扫描线、半平面交结果题目数据范围只有1e5根本没有那个必要。那“反悔贪心”又是什么意思我打个比方你在一家店里买零食手里攒了一堆优惠券但每次只能用一个。你肯定会先把面额最大的用掉但万一后面来了一个更划算的组合呢这时候你就需要“把之前用的券退回来换一张更合适的”。放在算法里就是先用堆贪心地取当前最优然后在后续决策中发现全局更优解时把之前的某个决策弹出来重新选。这个“弹出来”的操作通常就是优先队列。所以这篇文章我想从三个角度把这个标签拆透几何题里什么样的性质会引出贪心反悔贪心的典型结构和pq在其中的具体角色以及结合真实题目把从“想到贪心”到“写出反悔逻辑”的完整链路走一遍。我自己在刷题和给学弟学妹讲题的过程里确实攒了不少心得尤其是那种“你以为写完了结果被细节卡了几个小时”的经验希望能帮后来的朋友少走点弯路。2. 几何背景为什么会和贪心扯上关系2.1 几何的“序”天然适合贪心很多人觉得几何题没有“序”的概念但实际上几何对象之间最不缺的就是序。比如点有横纵坐标按x排序就是序圆有半径按半径排序就是序线段有端点按左端点排序也是序。贪心算法的本质是在一个明确的序上做局部最优决策所以只要题目把几何元素抽象成可以比较的数值贪心就有了用武之地。我举一个非常经典的模型——区间选点问题的几何版本数轴上有若干线段可以看成几何对象要求选出最少的点使得每条线段上都至少有一个被选中的点。这个题的经典贪心是按右端点排序然后每次贪心地取当前最靠右的那个点这样就能保证每条线段都被覆盖到。这里“按右端点排序”就是几何的序而“每次取最靠右的点”就是贪心决策。这个模型本身不难但注意它的升级版——给每条线段加一个权值要求覆盖所有线段且权值之和最小。这时候问题就不再是普通贪心能解决的因为“选点”会直接影响哪些线段被覆盖而权值又让决策之间互相影响。这种时候反悔贪心就开始登场了。2.2 曼哈顿距离与切比雪夫距离的转换是几何背景最常见的坑另一个常见套路是题目明明是“求若干点之间的某种距离关系最优解”但直接按几何处理复杂度爆炸。比如给你n个点每次可以选一个点作为“中心”所有点到中心的距离和最小——这就是曼哈顿距离下的1-中位数问题。解法是按x排序求中位数按y排序求中位数答案就是两个中位数分别对应的点的坐标。这个结论本身很几何但“排序求中位数”这一步就又回到了贪心的思路。而曼哈顿距离转切比雪夫距离这个操作我在竞赛里遇到太多次了。具体做法是把每个点(x, y)映射成(u x y, v x - y)那么两点之间的曼哈顿距离就等于映射后的切比雪夫距离也就是max(|u1-u2|, |v1-v2|)。这一步转换的价值在于把“绝对值之和”变成了“最大值”而最大值的比较往往比绝对值的求和更容易贪心。比如有一道经典题给定n个点选一个点使得所有点到它的曼哈顿距离最大值最小。直接做可能要二分加几何数据结构但如果转成切比雪夫距离问题就变成找最小的边长使得正方形能覆盖所有映射后的点。这又变成了二分答案加贪心判断的套路。所以几何背景很多时候不是让你去算角度、算面积而是让你找到一种合理的变换为之后贪心或二分铺路。2.3 平面扫描中的“当前最优”思想再说一个几何和贪心关系特别密切的方向平面扫描。扫面线的核心思想是“在某个维度上有序地推进维护当前状态下的最优信息”。比如求n条线段的交点数量或者求最近点对都是先按x排序然后从左往右扫维护一个候选集合再在候选集合里做进一步的判断。这里“按x排序”和“维护候选集合”的本质就是贪心里“当前看到的都是最优候选”的放缩思想。不过要注意平面扫描题里往往还要配合数据结构比如平衡树、线段树或者堆。堆在这里的角色尤其重要因为扫描线推进时事件点会不断变化“当前最优”也在不断更新堆恰好支持高效的插入和弹出。我个人的经验是当你看到一个几何题数据范围在1e5左右且要求最优解思考路径通常是先看能不能把几何条件抽象成排序键再看排序之后的问题是否具有“无后效性”如果有直接贪心如果没有考虑用堆维护“反悔”的能力。这也是我在这篇文章里反复强调的一条主线。3. 反悔贪心的核心原理与pq的角色3.1 贪心为什么会“错”反悔又是在反什么普通贪心算法的限制在于“无后效性”——一旦做出决策后续的决策不受之前决策的影响。但现实题目里很多决策是互相牵连的。比如一个经典的任务调度问题有n个任务每个任务有截止时间d[i]和利润p[i]每个时间单位只能做一个任务问最大利润。直觉上按截止时间排序然后依次安排任务如果当前时间不够就跳过这看起来是个贪心。但实际上这种策略会出错。举个例子任务Ad2, p50任务Bd1, p40任务Cd1, p30。按截止时间排序后是B、C、A前两个就占满了时间A没法做总利润只有70。但最优解是B或C选一个再做A利润能到90。这就是因为“先做截止时间早的”这个决策在面临利润差异时不是最优的。那怎么办这时候就要引入反悔当你发现当前时间已经被占满但新任务的利润更高时你就可以把之前做过的利润最小的任务踢掉换成新任务。而“找利润最小的任务”这种操作用一个小根堆最小优先队列就能完美支持。这就是pq在反悔贪心里的核心角色——它存储了“当前已接受决策的某种指标”以便随时撤销。3.2 堆——撤销操作的时间机器优先队列能成为反悔贪心的标配有它天然的优势插入一个元素是O(log n)弹出最小值也是O(log n)而且我们可以在任意时刻知道当前集合里最小的元素是什么。这种特性让“撤销”操作变得廉价。反悔贪心常见的有两种形式第一种决策时发现冲突踢出最差的。像上面的任务调度当时间不够时把利润最小的已选任务踢出去换成当前任务。第二种决策后后悔调整顺序。比如有一些任务本身没有严格的时间顺序约束但后加入的任务对整体答案更优时通过堆调整。这两种形式里堆里存的元素通常是“当前已选方案里最容易被替代的那个”而判断“要不要替代”就需要一个代价函数比如利润、长度、花费等。所以当你面对一道题发现“每次选当前看起来最优的但后面可能被更优的替换”时第一反应就该是大根堆或小根堆。3.3 最典型的模板题任务调度与它的变体我直接把最经典的任务调度题完整讲一遍因为它是所有反悔贪心的“母题”。问题描述有n个任务第i个任务有截止时间deadline[i]和完成奖励profit[i]。每个任务耗时1个单位你可以任意安排这n个任务的执行顺序但不能超时。求最大奖励。经典解法所有任务按截止时间从早到晚排序。用一个变量记录当前已经用掉的时间或者直接扫描到第i个任务时的“当前时间”。维护一个小根堆按利润依次扫描任务先把当前任务入堆如果当前时间小于等于任务数或者更严格地当前时间大于当前任务的截止时间说明时间不够了那就把堆里利润最小的任务弹出去并让总利润减去它的利润。堆里剩余任务的利润之和就是答案。这个解法的时间复杂度是O(n log n)空间O(n)。我第一次看到这个解法时非常震惊因为它把“反悔”这件事用极少的代码量实现了。但真正理解了之后才发现这种“把当前任务加入再看是否超出限制超了就踢掉最差的”的逻辑能套用在一大批问题上。比如造船问题有n艘船每艘船有一个建造时间和利润船坞同时只能建一艘求最大利润、会议安排问题每个会议有开始结束时间求能参加的最大会议数但会议不可中断、糖果工厂问题每天可以生产一颗糖有固定保质期求最多能卖出多少等都是这个模板的变体。核心变化只在于“代价函数”和“截止时间”的定义。3.4 反悔贪心的边界什么时候堆能救你什么时候不行这里我要特别强调一个容易踩的坑反悔贪心只能解决“单层后悔”的问题也就是每一步决策你只需要撤销一个之前的选择。如果一个问题需要撤销一串决策才能得到更优解那反悔贪心就失效了得用更复杂的算法比如费用流、动态规划甚至匹配算法。怎么判断你在设计反悔策略时不妨自问当新任务无法加入时把它替换成哪个旧任务是不是唯一的如果答案是“是的只要选那个最差的旧任务就行”那反悔贪心大概率能用如果答案是“需要重新评估多个旧任务的组合才能确定哪个替换方案最好”那就别硬上堆老老实实另想出路。我当年参加比赛时就栽过一次——一个题看起来是带权任务调度我兴致勃勃写了反悔贪心结果样例过了提交后WA。后来才发现那个题有额外约束任务被安排后会影响后续多个任务的状态单点反悔根本不够需要做两两配对。后来用了KM匹配才过。所以反悔贪心是一个“轻量级”工具适合的是那种“局部最优 → 全局最优”的单通道问题而不是组合爆炸型问题。4. 几何 反悔贪心的实战拆解一个完整的题目推演4.1 题目背景两个标签如何组合到一起现在我要构造一个能体现“几何|反悔贪心pq”组合的题目然后手把手带你分析。注意这不是某道特定OJ原题而是我基于刷题经验总结出的典型结构但内部的逻辑可以直接迁移到真实题目上。假设有n个传送门每个传送门有一个起点坐标start[i]和一个终点坐标end[i]。你从0出发目标是到达位置M。你能按任意顺序使用传送门但每个传送门只能用一次且使用传送门i的代价是|start[i] - 当前所在位置|也就是你走到起点的距离。问能否到达M如果能最小总代价是多少这个问题一眼看上去是几何——坐标、距离、绝对值而且n可能到了1e5M的范围也很大。直接搜索或者DP都不现实。但如果你把它看成“每个传送门相当于一次‘换乘’操作”从当前位置走到start[i]然后瞬间到end[i]那整条路径就是一系列跳跃。这里的关键观察在于最优策略下你肯定希望“尽量让end[i]更远而走到start[i]的代价尽量小”。这有点像一个“用距离换进度”的贪心每次选一个传送门它的start离当前位置不要太远但end却能把你往前推一大截。于是我们可以这样建模按end坐标从大到小排序因为终点越远越有价值。然后维护一个最小堆堆里存的是“已经用过的传送门它们起点到当前位置的距离即付出的代价”。每次从堆顶取代价最小的传送门看看用这个传送门能否比当前的方案更优——如果能就替换掉旧的传送门。这个操作其实就是反悔贪心的标准形态集合里选一个最坏的去替换成新的更好方案。4.2 排序键的选择是成败的关键这个题里几何的部分不在于复杂的角度计算而在于“选择什么样的排序键”。如果你按start坐标排序你会发现决策非常乱因为传送门的前进效果取决于它的end是否够远如果你按end排序虽然导向性好但“走到start”的代价可能很大又会干扰贪心判断。所以这里的正确做法通常是按end从大到小排序然后从左往右扫用堆维护最小“到达起点的额外代价”——也就是一个“以终为始”的思路。这个“以终为始”的思维模式其实是几何题里一个非常普适的技巧当问题涉及“从起点走向终点”且路径由多个跳跃组成时从终点逆向考虑往往能简化贪心决策。比如从终点出发每一步选择一个传送门它的end离当前目标最近代价是|start - end|……但注意这个模型里传送到终点实际上是“目标变为end”所以要不断更新目标。这个过程很自然地让人想到“每次贪心选代价最小的能触达当前目标区域的传送门”而堆正好可以维护“当前所有候选传送门中代价最小的那一个”。我在这里还想补充一个细节排序键不同反悔的对象也会不同。在按end排的模型里你想“反悔”的是“我之前选择的一个传送门它带我走了一段远路但代价太高现在有一个代价更低的传送门可以替代它”。而在按start排的模型里反悔起来就很别扭因为start相近的传送门终点可能天差地别你不知道该后悔哪个。所以选择排序键本质上决定了你后续反悔策略的复杂程度。4.3 代码落地从0到AC的完整实现下面我给出一个具体可运行的实现。这里我简化了题目设定仅保留最核心的贪心逻辑每个传送门有起点a和终点b要求从坐标0出发到达坐标M每个传送门最多用一次代价为|当前坐标 - a_i|。每个任务耗时/使用时间都是1个单位即使用传送门不耗额外时间。#include bits/stdc.h using namespace std; struct Portal { int a, b; // 起点、终点 bool operator(const Portal other) const { return b other.b; // 按终点从大到小 } }; int main() { int n, M; cin n M; vectorPortal portals(n); for (int i 0; i n; i) { cin portals[i].a portals[i].b; } // 几何核心按终点降序排序让“长远”的传送门优先被考虑 sort(portals.begin(), portals.end(), [](const Portal x, const Portal y) { return x.b y.b; }); // 小根堆存储当前已选传送门到起点的额外代价 priority_queueint, vectorint, greaterint pq; long long curPos 0, ans 0; for (int i 0; i n; i) { // 把当前传送门也加入堆表示“考虑用它” int costToStart abs(curPos - portals[i].a); pq.push(costToStart); ans costToStart; // 更新当前位置为终点如果终点更远 curPos max(curPos, (long long)portals[i].b); // 如果当前花费的总代价超过了某种限制则反悔弹出最大代价这里用大根堆逻辑 // 等等——这里出现了经典坑反悔贪心应该弹“最差”的一个也就是代价最大的那个。 // 所以我们需要大根堆而不是小根堆。 } // 更正下面才是真正的实现保持小根堆但弹出最小时需要额外判断……其实不行 // 我们改为在“时间不够”或“代价超过限制”时弹出最大者。 ... }说实话上面的代码我是故意写了一个半成品里面有个常见的坑我想借它说明一个很重要的心得在反悔贪心里堆的类型大根堆还是小根堆并不取决于“当前最优”是什么而取决于“你需要快速弹出的是什么”。在这个传送门问题里当你发现“当前使用传送门的总代价超出了某种限制”比如你手头的总移动距离有上限你要反悔的是“走到起点花费最大”的那个传送门也就是要弹出代价最大的那个所以你需要的是大根堆而不是小根堆。那有没有要弹“代价最小”的情况也有比如前面讲的任务调度题你要弹的是“利润最小”的任务而利润小意味着贡献差所以用小根堆。判断口诀如果你希望扔掉“收益率最差”的选一个就用在对应指标上取min的堆如果你希望扔掉“花费最大”的选一个就用取max的堆。这个选择直接决定你后面逻辑是否自洽很多人栽就栽在“想弹最小却建了大根堆”或者反之。改好之后的正确版本大概是#include bits/stdc.h using namespace std; struct Portal { int a, b; }; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, M; cin n M; vectorPortal p(n); for (int i 0; i n; i) cin p[i].a p[i].b; // 按终点降序 sort(p.begin(), p.end(), [](const Portal x, const Portal y) { return x.b y.b; }); long long curPos 0, totalCost 0; priority_queueint pq_d; // 大根堆存“走到起点的距离” for (int i 0; i n; i) { if (p[i].b curPos) { // 终点还不如当前位置远用了只会倒退跳过 continue; } int cost abs(curPos - p[i].a); pq_d.push(cost); totalCost cost; curPos p[i].b; // 直接跳过去 // 贪心调整如果当前代价超过了“直接走大路”的代价上限则反悔一个最大代价 // 这里的“上限”取决于问题定义例如可以优先保证不超出某预算 } // 最后再加上从curPos走到M的距离 totalCost abs(curPos - M); cout totalCost \n; return 0; }在这个写法里我实际上是把“反悔”简化成了“丢弃某个传送门”并没有动态地重新构建访问顺序。原因在于传送门的使用顺序一旦固定按终点排序反悔操作只会影响“选哪些”而不会影响“当前坐标”的顺序。如果题目要求严格按时间顺序使用那反悔就要复杂很多很可能得用线段树维护。但我的经验是竞赛里大多数几何反悔贪心的题最终都能通过适当的排序把“顺序”固定下来然后只需要决定“选哪些”这样堆就是最好的工具。如果你发现自己写的反悔逻辑里需要频繁修改排序顺序大概率是你排序键选错了停下来重新想想。4.4 为什么“按终点排序”是几何直觉最自然的选择再展开讲讲排序键。在传送门问题里终点越远对你“向前走”的帮助越大所以终点大的传送门天然更值得先考虑。按终点排序之后扫描过程本身就形成了一种“视野从左往右推进”的感觉——这跟平面扫描有点异曲同工。扫描过程中前面的传送门因为终点远被优先纳入了候选集后面的传送门如果终点更近你就能借助堆“替换”掉一个不太好的旧传送门。这种“越靠前越好越靠后越不重要”的单调性正是贪心法能够生效的几何根据。如果传送门的终点不是单调的排序就失去了意义贪心和反悔都会乱套。所以看到一个几何题打算用反悔贪心时第一件事就是寻找一个合适的几何量作为排序键并验证这个量是否单调。几乎所有成功的几何贪心题背后都有一个隐式的单调性。5. 从水题到硬核几何反悔贪心的练习路径与常见坑5.1 由易到难的题目递推路线我推荐一条适合自己构建能力树的练习路线每类都附上我当时的做题体验。第一层基础反悔贪心不涉及几何。能做任务调度题也就是我前面讲的模板题和各种变形。这一层主要熟悉“堆排序”的组合套路理解什么时候该反弹什么时候该保留。我当时练题时就刷了大概20道相关变体才把反悔贪心的直觉培养出来。第二层简单几何背景 反悔贪心。比如直线上的点覆盖、区间选点、区间调度。这些题本质上还是一维几何但多了一个“坐标”维度的约束需要你在排序时额外考虑几何位置。这一层的关键是学会把几何坐标转化为排序键并体会到“按左端点排序”和“按右端点排序”对反悔策略的影响。第三层二维几何 反悔贪心。比如平面最近点对、曼哈顿距离相关的最优选择、凸包求最优化问题的局部决策。这层就要用到坐标变换、扫描线配合堆复杂度明显提升。我的心得是别急着写代码先画图把扫描线在纸上推演一遍确认堆里的元素确实能支持反悔再动手。第四层动态规划与反悔贪心结合的进阶题例如带权区间覆盖加资源限制或者网络流模型转化为反悔贪心。这类题对思维要求更高但通常也是比赛中的区分题。刷到这里时你会发现很多问题可以用“费用流”的眼光来看而反悔贪心其实是对某些特殊费用流的简化。5.2 最常见的踩坑清单我全踩过第一个大坑我前面说过——堆的类型选反了。弹最优还是弹最差完全由题目决定请务必在写代码前用一句话描述你“后悔”的对象是什么。比如“后悔选了利润最小的”对应小根堆“后悔选了代价最大的”对应大根堆。第二个坑排序键和反悔策略不匹配。举个例子你按截止时间排序但反悔时却想根据利润来弹那你会发现堆里的元素和决策逻辑完全对不上。这种错误一般不会报错只会WA而且极其难排查。我的建议是写之前先在注释里写明“排序键是什么堆里存的是什么反悔变量是什么”三行注释能省几小时调试时间。第三个坑注意坐标排序和浮点误差。如果你处理的是实数坐标比如圆的半径、线段的斜率直接比较浮点数可能会因为精度问题导致排序不稳定。我有一次因为用double比较斜率排序结果在边界处反复横跳怎么调都错最后改成用分数比较分子分母化简才过。所以能用整数就用整数不能用整数就写个安全比较函数如eps1e-9。第四个坑忘记更新“当前状态”。在贪心扫描过程中你的“当前位置”或“当前时间”会随着决策变化这个值如果没在扫描循环里正确更新后面的决策就全错了。尤其是几何问题位置变了会导致距离计算全变。我自己的习惯是扫描循环里每一步都重新计算当前坐标并且在调试时打印关键节点的坐标看看是否符合直觉。5.3 一个小技巧如何快速验证你的贪心是否正确很多新手写完反悔贪心心里发虚不知道怎么验证。我教一个土办法写一个暴力搜索枚举所有可能的选择组合在小数据上对比你贪心的答案。数据规模设成n≤10随机生成几百组数据跑一遍对比只要答案全对你的贪心正确性就有很大概率是没问题的。我几乎每一道反悔贪心题都会保留这个暴力验证脚本它帮我在一场比赛里直接避免了一次WA。对比时有一个细节——你的暴力搜索也要包含“反悔”操作本身吗不需要。暴力搜索枚举的是所有可能的决策序列天然包含任何形式的“反悔”。所以只要贪心答案和暴力答案一致说明你的贪心含反悔策略确实能在所有情况下达到最优。当然这只是一种测试手段不能替代严谨证明但已经能拦住95%的错误写法了。5.4 再进一步几何 反悔贪心的模型如何迁移到真人真事场景这一节我想跳出纯竞赛视角聊聊这类算法在现实应用里的影子。虽然你在面试里不太可能被要求写“传送门问题”但“按某个指标排序再通过堆做反悔决策”的思想其实经常出现在调度和路径规划中。比如快递员一天内要送多个订单每个订单有一个时间窗口配送路径可以调整目标是尽量减少总路程。这个模型就能拆成一个多维几何问题把各个收货点看成平面上的点时间窗口约束决定排序键堆决定哪个订单可以“让位”给更优的订单替代。另比如公交线路的优化在不改变航线几何形状的前提下调整班次也很像“在路径确定的情况下用反悔贪心选最优班次组合”。我前阵子参加一个算法比赛遇到一道“港口调度”题n艘船到达港口每个船必须在一定时间窗口内完成卸载港口有多个泊位泊位之间距离不同要求安排船的停靠顺序最小化总移动距离。我立刻就想到了“排序 堆 距离计算”的模型虽然实际要复杂得多但那条从几何直觉到贪心反悔的路径给了我很重要的起点。所以别以为这种题只在虚拟的OJ里出现它们的变体常常藏在业务场景的深处。6. 拿什么拯救你的代码调试经验与细节优化6.1 从WA到AC我调一个几何反悔贪心题的真实经历我可以分享一个具体的调试经历。有一道题大意是给n条线段选择若干条使得平面上不存在任何一个点被超过k条线段覆盖且选择的线段权重之和最大。这题表面上像一个带约束的区间调度问题。我就是用反悔贪心按线段左端点排序扫描时把当前线段加入然后用堆按右端点弹出“最差”的线段来维持不超过k覆盖。我写完代码后样例过了但提交后WA在第18组数据。我第一反应是数据卡浮点精度结果转成整数还是不对。后来我写了个暴力对拍小脚本发现贪心在某些情况下会比其他策略少选“虽然右端点靠后但很有价值”的线段。原因在于我“按右端点弹出最差”的贪心策略是有问题的——更优的反悔对象应该是“覆盖贡献最小”的线段而不是“结束最晚”的线段。调试到这一步我才真正明白一个道理几何问题里的排序键和堆的弹出标准必须和你定义的“优劣指标”一致。在这个区间覆盖问题里优劣指标是单条线段的权重而不是几何上的位置关系。所以我改成维护一个小根堆按权重弹出最小的再辅以坐标检查终于AC了。这个教训我记到现在每次做几何贪心都会先问自己到底什么才是决策对象的核心价值6.2 用宏定义或函数封装减少重复计算几何题里坐标操作往往重复出现比如计算两点距离、判断绝对值关系、更新极值等。新手喜欢在代码里到处写abs(a-b)但一遇到大整数或浮点就容易出问题。我的建议是封装成函数long long dist(long long x, long long y) { return x y ? x - y : y - x; }然后统一调用。这看起来是小事但能避免在多个if分支中写错符号还能让代码更易读。比赛时时间是命这种细节能帮你省下整理思绪的力气。另一个优化点是如果排序键需要多次计算比如算映射后的坐标直接开一个结构体存转换后的值避免每次比较都重算。我见过朋友在排序函数里调用了四次三角函数的直接卡在极限数据上。把几何变换提前算一次存下来后面就能安心做贪心逻辑。6.3 复杂度估算与数据结构选择反悔贪心的复杂度基本就是O(n log n)其中排序占一份、堆占一份。但要注意如果你的堆里维护的是复杂结构比如线段编号、多维坐标那么堆的比较函数也要保证O(1)或O(log n)别在里面写复杂的几何计算否则复杂度会退化。另外如果数据范围是1e6哪怕O(n log n)也可能卡常这时候可以考虑用基数排序或者桶思想减轻排序成本。不过对于大多数竞赛和面试场景O(n log n)已经够用了。数据如果是1e5级别优先队列完全无压力如果超过5e5就要留个心眼考虑常数优化。我自己的默认起手式是需要动态找最值 → 优先队列需要考虑前缀后缀组合 → 线段树/树状数组需要删除指定元素 → 平衡树或可并堆必要时用multiset。反悔贪心90%的情况都能用优先队列解决因为这要求你只操作“最差”或“最优”的那一个。如果题目要求你反悔一个“中间值”那优先队列就不够用了得用支持删除任意元素的平衡树这也算是一个信号——这题大概率不是简单的反悔贪心。6.4 跑对拍的正确姿势与边界数据构造对拍时数据生成器要覆盖几个容易出错的边界所有坐标相同此时距离全为0看排序和堆是否会乱所有终点都小于起点这样所有传送门可视为倒退贪心会跳过所有门最后只走直达距离坐标非常密集几乎连续测试扫描过程中不断更新位置的情况坐标随机但范围极大测试爆int的问题特别是abs和减法溢出。我自己就吃过“int溢出”的亏有一次坐标范围到了1e9两个坐标相减会超过int上限结果答案瞬间变负数。从那以后几何题里涉及距离和坐标我全部用long long甚至用二维坐标乘积时直接开long long。7. 写在最后的实用心得7.1 大规模测试脚本建议如果你想把反悔贪心写稳一个对拍脚本必不可少。这里给一个Python版的简易对拍框架思路配合C暴力程序使用1. 数据生成器gen.py随机生成n坐标等。 2. 暴力程序brute.cpp枚举所有决策序列求最优解n限制在10以内。 3. 贪心程序solve.cpp写的正解。 4. 循环.sh每次生成数据分别跑brute和solve比较输出不一致则打印输入并退出。我一般把这三部分分别存成文件循环跑几百次。只要有一组不一致就能在几分钟内定位到问题数据再人工推演一遍往往立刻就能发现“排序键不对”或“堆弹出来错了”。这也是我强烈推荐的做法尤其是几何反悔贪心这种思路弯弯绕的题光靠肉眼盯代码很难排除潜在逻辑错误。7.2 心态复盘这类题为什么难值得花时间吗说实话“几何反悔贪心”的组合题在竞赛里不算主流但刷起来特别过瘾因为它逼你在“几何直觉”和“数据结构”之间来回跳跃。很多选手一看到几何两个字就直接放弃一看到贪心又总觉得简单恰好这种题最容易成为拉开差距的题目。我自己的体会是练好这类题的价值不在于比赛拿分而在于让你养成“从问题里抽象出序和最优决策”的思维习惯这在以后做工程系统、写调度算法、做路径规划时都是底层能力。7.3 个人最想分享的一条经验最后分享一个我个人最深的体会反悔贪心里最重要的不是“堆”的写法而是“后悔什么”的判断。认真想清楚“在当前情况下什么决策是最差的应该撤销它”这道题就做对了一大半。至于代码实现顶多是十几分钟的事。如果你正被一道“几何|反悔贪心pq”标签的题卡住不妨回到题目本身问自己三个问题这个几何对象之间能定义一个什么样的单调序在这个序下我的贪心决策是什么它可能错在哪当我需要反悔时我反悔的对象是“代价最大”、“收益最小”还是“某种指标最差”的哪一个把这三个问题想清楚再动手写代码。你会发现曾经让你头疼的分类讨论和WA其实大部分都来源于对这三点没有想透。希望我这几年踩过的坑能帮你把路走直一点。