专题：排序的应用与贪心

本讲定位：基础算法系列第 03 讲。basic-series/01-prefix-sum-difference.md 第 3 行写着：

「前缀和与差分是 CSP-J 复赛出现频率最高的两个技巧之一，另一个是排序。」

本讲就是那另一个。 但排序的实现已经讲过三遍了（cspj-series/cspj-08 的八大排序与稳定性、gesp-series/gesp4-05 的三剑客手工模拟、gesp5-07 的归并与快排），本讲一律不重讲。本讲讲的是考场上真正用到的那一层——比较器怎么写、多关键字怎么排、什么时候必须 stable_sort——以及排序最大的下游客户：贪心。

贪心这块，gesp5-08 讲过”什么是贪心”。本讲补的是它没讲的那一半，也是贪心真正难的地方：

怎么知道一个贪心是对的？以及怎么把一个”看起来对”的贪心打掉？

本讲实测（六组，都在正文里）：

⚠️ 比较器写成 <= 是未定义行为，崩不崩取决于内存布局——同一份代码换个运行环境结论就变：每次开一个独立进程跑，$n\ge17$ 就 5/5 全崩；而在同一进程 fork 出的子进程里跑，要到 $n=10^5$ 才崩（$n\le1000$ 全过）。两种环境唯一共同的是：$n\le16$ 从不崩（走的是插入排序路径）。而元素互不相同时，$n=10^6$ 也一次不崩。

sort 打乱相等元素的阈值也是 16/17：$n\le16$ 时保序 100%，$n=17$ 时保序 0.0%。（同一个原因：libstdc++ 的 sort 在 $n\le16$ 时走的就是插入排序。）

stable_sort 的代价只有 1.15 倍（500 万条记录：0.4940 s vs 0.5661 s），但要 $O(n)$ 额外空间。

⚠️ 0/1 背包按性价比贪心的最小反例只要 2 件物品：容量 2，物品（重量/价值）= 2/3 与 1/2，贪心得 2、最优 3。随机数据上错 5.50% / 12.41% / 17.67%。

区间调度三种排序策略：按结束时间（正确）全档 0.00%；按开始时间 3.50% / 15.70% / 31.87%；按区间长度只错 0.81% / 2.00% / 3.33%——正因为它”几乎总是对”，才最危险。找零钱贪心的最小反例是币值 $\{1,3,4\}$ 凑 6（贪心 3 枚，最优 2 枚）。

交换论证可以直接验：在 94 989 个”相邻逆序对”上各做一次交换，变好 94 989 次、变差 0 次——这正是交换论证要的那句话。反悔贪心（小根堆）全档 0.00%，而”按收益降序只占截止那一格”的写法错 32.38% / 58.09% / 75.60%。

文中所有带 int main 的完整程序均经 g++ -std=c++11 -Wall 编译运行，文中标注的输出就是实测输出。

前置：排序的实现与稳定性（cspj-series/cspj-08、gesp-series/gesp4-05、gesp5-07——本讲不重讲）；gesp-series/gesp5-08（贪心是什么，本讲从”怎么证明它对”开始）；ds-series/03（二叉堆——第 3.2、3.3 节要用）；第 02 讲（二分答案的 check 里常常是一个贪心）。

适合对象：标 J。大纲【3】贪心法、【3～6】排序。J 组复赛最高频的两个技巧之一；第 3.3 节（反悔贪心）与第 4 节的证明部分标 ⭐，是 S 组增量。

1. 排序不是”会调 `sort`“就够了

排序在考场上有两个身份：

它自己是答案的一部分——“按某种规则排好序再输出”；
它是别的算法的预处理——贪心、二分、双指针、离散化、扫描线，全都以”先排个序”开头。

而这两件事真正的难点都不是”怎么排”，是**“按什么排”和“排完之后相等的怎么办”**。本讲第 2 节处理这两件事，第 3、4 节处理它最大的下游客户。

2. 排序的应用层

2.1 三种比较方式

sort(a, a + n);                       // 一、用元素自带的 operator<
sort(a, a + n, cmp);                  // 二、传一个比较函数
sort(a, a + n, [](A x, A y){...});    // 三、传一个 lambda（C++11 起）

结构体排序的两种常见写法：

struct Rec { int key, id; };
// 写法 A：重载 operator<（这个类型"天生"就有默认顺序时用）
bool operator<(const Rec &a, const Rec &b) { return a.key < b.key; }
// 写法 B：写比较函数（同一个类型要按不同规则排好几次时用）
bool byKey(const Rec &a, const Rec &b) { return a.key < b.key; }
bool byId (const Rec &a, const Rec &b) { return a.id  < b.id;  }

一句话选型：只有一种排序规则就重载 operator<；有多种就写多个比较函数。 别在 operator< 里塞一个”万能”的复杂规则，那会让代码变得无法阅读。

2.2 多关键字：两种写法

「按 key 升序；key 相同时按 id 降序」——两种做法：

// 写法一：一次 sort，比较器里分层
bool cmp(const Rec &a, const Rec &b) {
    if (a.key != b.key) return a.key < b.key;   // 主关键字
    return a.id > b.id;                          // 次关键字
}
// 写法二：两次 stable_sort，从【次】关键字排到【主】关键字
stable_sort(v.begin(), v.end(), byIdDesc);       // 先次
stable_sort(v.begin(), v.end(), byKey);          // 再主 —— 必须 stable！

写法一更常用（一次排序，快）。写法二在关键字很多、或者规则是运行时才确定时更清晰——代价是必须每次都用 stable_sort，用 sort 就会把前一次的成果毁掉。

专题：排序的应用与贪心

1. 排序不是”会调 sort“就够了

2. 排序的应用层

2.1 三种比较方式

2.2 多关键字：两种写法

1. 排序不是”会调 `sort`“就够了