算法——贪心算法-EW帮帮网

1. 导引问题

1）例题:硕鼠交易

问题背景：老鼠准备用猫粮与看守仓库的猫进行交易，仓库有多个房间，每个房间的猫明码标价不同数量的猫粮换取豆子。
关键规则：
- 可选择任意房间交易，可全部交换或按比例部分交换
- 示例数据：老鼠有5单位猫粮，三个房间分别需要：
  - 房间1：7单位豆子 ↔ 2单位猫粮
  - 房间2：4单位豆子 ↔ 3单位猫粮
  - 房间3：5单位豆子 ↔ 2单位猫粮
解题核心：
- 性价比计算：单位猫粮能换取的豆子量（性价比=猫粮量/豆子量）
- 交易策略：优先选择性价比高的房间交易（示例中房间1性价比3.5最高）
实现关键：
- 需要掌握结构体数组排序（按性价比降序排列）
- C语言基础要求：熟练使用qsort函数进行自定义排序

2. 初识贪心算法

基本定义：在对问题求解时，总是做出在当前看来是最好的选择（局部最优解）。
算法特性：
- 不保证全局最优，需要具体问题具体证明
- 适用于具有"贪心选择性质"的问题（如硕鼠交易问题）
实例分析：
- 在硕鼠交易中，每次选择当前性价比最高的房间就是典型的贪心策略
- 该问题的贪心选择性质：局部最优能导致全局最优
实现要点：
- 需要先对所有选项进行排序（时间复杂度主要取决于排序）
- 适合用结构体存储多属性数据（如房间的豆子量、猫粮量、性价比等）

3. 应用案例

1）例题:田忌赛马

问题背景：春秋战国时期齐王与田忌赛马，双方各有三匹马且速度各不相同，输者需支付200元。
贪心策略：
- 当田忌最好的马比不过对方时，用最差的马与之比赛（如用74对95），保留更好的马用于后续比赛
- 当田忌有马能胜过对方时，立即用能胜的最弱的马取胜（如用92对87）
生活实例：篮球比赛中用两个不会打球但体能好的队员专门盯防对方最强球员，相当于"用最差的马换对方最好的马"
常见误区：
- 狭隘认为必须按"最差对最好、中等对中等、最好对最差"的固定模式
- 实际上应根据具体马速灵活选择能赢则赢的策略

2）例题:事件序列问题

问题描述

定义：给定N个事件的开始和结束时间，找出最多能参加的不重叠事件数量，这里要的是数量多，不是时间长
生活实例：电视频道转播不同体育赛事，求最多能完整观看的节目数量
错误贪心策略：
- 选择最短事件：反例[11-13],[0-12],[12-24]，选短事件会导致只能看1个
- 选择最早开始：反例[0-7],[1-7]，选最早开始只能看1个
正确解法

正确策略：每次选择结束时间最早且不与已选事件冲突的事件，贪心算法的关键是选择 “局部最优” 以达到 “全局最优”。对于事件选择问题，优先选结束时间早的事件是最优策略 —— 因为结束早意味着后续可安排的事件更多。
证明方法：
- 命题：至少存在一个最优解包含最早结束事件
- 反证法：假设所有最优解都不含最早结束事件，可通过替换构造矛盾
算法步骤：
- 将所有事件按结束时间排序
- 依次选择结束最早且不冲突的事件
完整分析：
- 排序后，事件按结束时刻从小到大依次为：事件 0（结束 3）、事件 1（结束 4）、事件 2（结束 7）、事件 3（结束 8）、事件 4（结束 9）、事件 5（结束 10）、事件 6（结束 12）、事件 7（结束 14）、事件 8（结束 15）、事件 9（结束 18）、事件 10（结束 19）、事件 11（结束 20）。
- 筛选不重叠事件：
  - 选事件 0（结束 3）→ 下一个事件 1 发生时刻 3 ≥ 3，选中；
  - 事件 1 结束 4 → 事件 2 发生时刻 0 < 4，跳过；事件 3 发生时刻 3 < 4，跳过；
  - 事件 4 发生时刻 2 < 4，跳过；
  - 事件 5 发生时刻 5 ≥ 4，选中；
  - 事件 5 结束 10 → 事件 6 发生时刻 6 ≥ 10？否，跳过；
  - 事件 7 发生时刻 4 < 10，跳过；
  - 事件 8 发生时刻 10 ≥ 10，选中；
  - 事件 8 结束 15 → 事件 9 发生时刻 8 < 15，跳过；
  - 事件 10 发生时刻 15 ≥ 15，选中；
  - 事件 10 结束 19 → 事件 11 发生时刻 15 < 19，跳过。
- 最终选中事件编号为 [0, 1, 5, 8, 10]，长度为 5。
注意事项：
- 最长序列长度唯一，但具体序列可能有多个（如可选10号或11号事件）
- 贪心算法与排序密切相关，通常需要先对数据进行排序
实现要点
- 排序关键：使用结构体数组存储事件，按结束时间排序
- 贪心本质：每次局部最优选择（最早结束）导致全局最优解
- 生活类比：如同卖红薯时每次都挑最熟的，或吃苹果时每次都选看起来最好的

3）例题:搬桌子问题

问题描述

场景设定：公司在一栋楼内，楼中间是走廊，两边各有200个房间，一边为单数编号，一边为偶数编号。
任务要求：需要将桌子从一个房间搬到另一个房间，走廊非常窄，同一时间只能搬一个桌子，搬一趟固定耗时10分钟。
冲突判定：如果两个搬家任务需要使用同一段走廊，必须分两趟进行，就是不能交叉重叠，重叠就必须分趟，如果没有重叠就可以同时执行
输入输出理解
- Sample Input（输入）：
  - 第一行的3表示一共有三组大任务，这个是大的整体
  - 后面的4，2，3表示每一组里面有多少个搬家任务
  - 后面的就是具体的搬家任务，比如10-20，30-40，50-60，70-80
- Sample Output（输出）：
  - 输出的10、20、30，就是最终每组任务的总耗时。
解题思路
- 方法一：贪心算法
  - 核心思路是：优先安排 “结束位置早” 的搬桌任务
  - 贪心策略：按 “目标房间号” 升序排序所有任务。每次选择 “未被安排且目标房间最早” 的任务，然后跳过所有与该任务走廊区间重叠的任务 —— 因为先完成早结束的任务，能为后续任务留出更多 “不冲突” 的时间。
  - 算法步骤：
    - 整理任务：将所有搬桌任务的 “起始房间” 和 “目标房间” 存储为区间（需统一为左小右大，比如从 10 搬到 20，区间是 [10,20]；从 30 搬到 20，区间调整为 [20,30]）。
    - 排序任务：按 “目标房间号” 升序排序所有区间。
    - 遍历安排任务：
      - 初始化 “已安排的最后一个任务的目标房间” 为 0。
      - 遍历排序后的任务，若当前任务的 “起始房间” > 已安排的最后一个目标房间（说明无冲突），则选中该任务，并更新 “已安排的最后一个目标房间” 为当前任务的目标房间。
  - 计算总耗时：总耗时 = 选中的任务数（趟数） × 10 分钟。
- 方法二：区间标记法
  - 核心思想：把走廊的每个位置抽象成数组的 “下标”，搬桌子的任务抽象成 “对一段下标区间的计数”。最终，数组中最大的计数值就是 “同一时间最多有多少个任务需要占用同一段走廊”，而这正是需要的最少趟数（因为每趟只能处理一个任务，最多重叠的任务数就是最少需要的趟数）。
  - 步骤详解：
    - 走廊位置与数组下标的映射
    - 因为房间是 “单数在一边，偶数在另一边”，为了让对称的房间（如 1 和 2）对应数组的同一个下标，采用技巧：(房间号 - 1) // 2。
      - 示例：房间 1 → (1-1)//2 = 0；房间 2 → (2-1)//2 = 0；房间 3 → (3-1)//2 = 1；房间 4 → (4-1)//2 = 1…… 这样就把对称的房间映射到了同一个数组下标，方便统计走廊的占用。
    - 任务的区间标记
    - 对于每个搬桌任务（从房间s到房间d）：
      - 先统一区间为 “左小右大”（如果s > d，就交换s和d，保证区间是[s, d]）。
      - 然后将s和d转换为数组下标（用(房间号 - 1) // 2），得到区间[start_idx, end_idx]。
      - 对数组中start_idx到end_idx的所有下标，执行count[i] += 1（表示这个位置被占用的次数 + 1）。
    - 计算最少趟数
    - 遍历数组，找到最大的计数值max_count，这就是 “同一时间最多有多少个任务重叠”。因为每趟只能处理一个任务，所以最少需要max_count趟，总耗时 = max_count × 10分钟（每趟 10 分钟）。
代码逻辑

#include <iostream>
using namespace std;

const int MAX = 200; // 走廊最多对应200个下标（因为有400个房间，(400-1)//2 ≈ 199.5 → 取200）
int count_[MAX] = {0}; // 记录每个走廊位置的占用次数

int main() {
    int T;
    cin >> T; // 任务组数
    while (T--) {
        int s, d;
        cin >> s >> d;
        // 统一区间为左小右大
        if (s > d) {
            int temp = s;
            s = d;
            d = temp;
        }
        // 转换为数组下标
        int start = (s - 1) / 2;
        int end = (d - 1) / 2;
        // 标记区间内的每个位置，占用次数+1
        for (int i = start; i <= end; i++) {
            count_[i]++;
        }
    }
    // 找最大的占用次数
    int max_count = 0;
    for (int i = 0; i < MAX; i++) {
        if (count_[i] > max_count) {
            max_count = count_[i];
        }
    }
    // 总耗时 = 趟数 × 10分钟
    cout << max_count * 10 << endl;
    return 0;

但是贪心算法是有局限的，单纯‘每趟尽可能多搬桌子’的贪心策略在某些情况下无法得到最优解，需要更系统的区间重叠分析方法

为什么怎么说呢？

我们举一个例子来理解一下

假设有 3 组任务：

任务 1：走廊区间 [1, 20]（长区间，占用大段走廊）。
任务 2：走廊区间 [21, 30]（与任务 1 无重叠）。
任务 3：走廊区间 [2, 19]（完全包含于任务 1）。
任务 4：走廊区间 [22, 29]（完全包含于任务 2）。

贪心的逻辑是 “当前趟尽可能多选不冲突的任务”。

第 1 趟：优先选 “数量多且不冲突” 的任务 1 和任务 2（共 2 个，无重叠）。
第 2 趟：任务 3 只能和任务 1 冲突（需单独一趟），任务 4 只能和任务 2 冲突（需单独一趟）→ 因此需要第 2 趟和第 3 趟，分别搬任务 3、任务 4。
总趟数：3 趟，总耗时 3 × 10 = 30 分钟。

区间标记法中，“小任务（如 2 - 19、22 - 29）” 和 “大任务（如 1 - 20、21 - 30）” 的重叠统计是全局的：小任务的重叠数（如 1 - 20 与 2 - 19 重叠数为 2）直接决定了 “这一段需要 2 趟”；大任务若能覆盖小任务且自身无新冲突，就可 “合并到后续趟数”

第 1 趟：搬任务 3（[2, 19]）和任务 4（[22, 29]）→ 两者无重叠，可同时搬。
第 2 趟：搬任务 1（[1, 20]）和任务 2（[21, 30]）→ 两者无重叠，可同时搬

贪心算法是优先安排结束位置早的任务，尽可能在不冲突的情况下完成更多的任务，由于任务一和二组成了最长序列，其他两个任务都在这期间，就必须单独分开，就像不重叠序列问题，先找最早结束的时事件，然后再按顺序一个一个比较，如果出现重叠的事件就必须单独，1-3，3-4，5-10，那么0-7和4-14就必须单独，但是区间标记法是直接计算最大重叠冲突数，比如1-20和2-19占用同一段，为2，21-30和22-29占用同一段，为2，所以要分开完成，为两趟，这就是“先处理小区间任务，为后续大区间任务留合并空间”，先把小的分好，大的能合并过来的就合并，有点像分了两趟计算的贪心算法，但是贪心算法是一趟按顺序全部分好全部趟次

简单来说就是：一个是先安排局部，导致小任务被拆分，一个是全局安排，全部安排好，考虑 “小任务先处理后，大任务能否合并” 的情况，这样就不会在中间把某个任务拆分出来

比喻一下：

1. 贪心算法（局部安排）：像 “走一步看一步” 的规划

可以把贪心算法理解成 “按顺序排任务，排到哪算哪”：

它先按 “结束早” 的规则选第一个任务（比如大任务 1），再选下一个不冲突的（比如大任务 2），这一步的 “局部最优” 是 “当前能多安排两个任务”。

但它没考虑 “后续小任务（3、4）会被这两个大任务‘包在里面’”—— 就像先占了大房间，小家具只能等大房间空了再一个个往里放，自然会被拆分成多趟。

本质是 “局部选择优先，全局冲突后知后觉”，所以可能出现 “为了当前多安排，导致后续任务被迫拆分” 的情况。

2. 区间标记法（全局安排）：像 “先画热力图，再分批次”

区间标记法更像 “先把所有任务的走廊占用情况画成一张‘热力图’”：

每个走廊位置被多少任务占用（比如2-19和1-20重叠的位置，热力值是 2；22-29和21-30重叠的位置，热力值也是 2）。

这张 “热力图” 直接告诉我们：整个走廊最拥挤的地方，最多有 2 个任务同时需要—— 所以最少只需要 2 趟（每趟处理 1 个 “拥挤点” 的任务）。

至于 “先处理小任务还是大任务”，其实是 “热力图” 的自然结果：因为小任务和大任务的重叠区域热力值是 2，所以必然要分 2 趟；而同一趟里，只要任务不重叠（比如小任务 3 和 4、大任务 1 和 2），就能合并安排。

本质是 “全局冲突先知先觉，直接按最大冲突数分趟”，所以不会出现 “后续任务被迫拆分” 的情况 —— 因为所有冲突都提前算好了，每趟安排的都是 “无冲突的任务组合”。

总之：

贪心算法因 “局部优先”，可能在排完大任务后，让小任务陷入 “被大任务包围” 的困境，只能拆分；

区间标记法因 “全局统计冲突”，提前知道 “最多需要分几趟”，再在每趟里安排不冲突的任务（无论大小），自然能让小任务和大任务分别合并，避免拆分。

两种方法的核心差异，就是 “是否提前看清了所有任务的全局冲突关系”。

4）例题:最小新正整数

贪心策略分析
- 错误策略: 直接删除最大数字可能得到错误结果，如213删除1位时，删除3得21，但删除2得13更优。
- 正确思路: 高位数字越小越好，应从左到右处理。
具体实现方法
- 核心逻辑：
  - 要让新数最小，高位数字越小越好（因为高位权重远大于低位）。因此，需从左到右扫描数字串，优先删除 “破坏递增趋势” 的较大数字
- 核心算法:
  - 从左到右扫描数字串
  - 当发现当前数字大于下一个数字时，删除当前数字
  - 每删除一个数字算作"一趟"
- 特殊情况处理: 若整个序列递增(如123)，则直接删除最后s位
- 实现技巧:
  - 使用标记数组而非实际删除元素
  - 每趟处理后需重新从头开始扫描
具体案例分析：
- 原数字串：1 7 8 5 4 3 （删除4位）
  - 第 1 趟：扫描到7时，7 > 8不成立；扫描到8时，8>5成立，删除8，剩余1 7 5 4 3。
  - 第 2 趟：扫描到7时，7 > 5成立，删除7，剩余1 5 4 3。
  - 第 3 趟：扫描到5时，5 > 4成立，删除5，剩余1 4 3。
  - 第 4 趟：扫描到4时，4 > 3成立，删除4，剩余1 3，最终得到最小新数13
- 原数字串：1 7 8 5 3 4 （删除4位）
  - 第 1 趟：扫描到7时，7 > 8不成立；扫描到8时，8>5成立，删除8，剩余1 7 5 3 4。
  - 第 2 趟：扫描到7时，7 > 5成立，删除7，剩余1 5 3 4。
  - 第 3 趟：扫描到5时，5 > 3成立，删除5，剩余1 3 4。
  - 第 4 趟：当前序列已经是递增序列，但是还要删除一位，s=1，直接删除最后一位即可
- 原数字串：1 2 3 4 5 （删除2位）
  - 要删除 2 位，因为整个序列是递增的，没有 “当前数字> 下一个数字” 的情况，所以直接删除最后 2 位，得到1 2 3，这就是最小的新正整数

5）例题:青蛙邻居

问题理解
- 场景描述: 城市有多个湖泊，每个湖泊住一只青蛙，相连湖泊的青蛙互为邻居。
- 问题转化: 给定每个青蛙的邻居数量(度数序列)，判断是否存在对应的图结构
解题思路
- 常见误区: 仅通过度数之和的奇偶性判断(错误)
  - 反例1: 度数序列[2,2,1]和为偶数但不可能
  - 反例2: 度数序列[1,1,0]和为偶数且可能
  - 反例3:度数序列[4,4,2,1,1]为偶数但不可图化
- 度数之和的奇偶性是图存在的必要条件（因为每条边贡献 2 个度数，总度数必为偶数），但不是充分条件，存在度数和为偶数，但仍不可图化的情况
- 正确解法: 需要满足图论中的度数序列可图化条件(Havel-Hakimi定理)
  - 度数序列排序后，删除最大度数d，并将接下来的d个数各减1
  - 重复直到所有数为0(可图化)或出现负数(不可图化)
实例分析
- 示例1: [2,2,2] → 可图化(三角形)
- 示例2: [2,2,1] → 不可图化
- 示例3: [1,1,0] → 可图化(一条边加孤立点)

可图化

定义：可图性判定是指判断给定度序列能否构造出对应无向图的性质。"可图"作动词用，表示可以画出图的意思，就是只要能根据给定的度数序列构造出一个合法的图结构就可以
示例：
- 可图序列：
  2,2,2,1,1,02,2,2,1,1,02,2,2,1,1,0
- 不可图序列：
  2,2,0,2,12,2,0,2,12,2,0,2,1

Havel-Hakimi定理

定理内容：非增序列S:d1,d2,...,dn是可图的，当且仅当序是可图的。
操作要点：
- 每次对序列进行递减排序
- 去掉第一个数d1
- 将后续d1个数各减1
- 重复直到出现全0序列（可图）或负数（不可图）
原理：
- Havel - Hakimi 定理的本质是通过一系列的操作来模拟图的构造过程。
- 排序：将度数序列按非递增顺序排列（从大到小排），是为了先处理度数最大的顶点。在构造图的过程中，度数最大的顶点对图的结构影响较大，先处理它能更好地确定后续顶点的连接情况。
- 删数与减度：取出最大度数d，删除它并将接下来的d个数各减 1，就是把跟刚才删掉的顶点有连接的顶点度数减一，这个操作相当于在图中构造了一个度数为d的顶点，并让它与度数序列中接下来的d个顶点分别相连。因为这d个顶点与新构造的顶点连边了，所以它们的度数都要减 1。
- 重复验证：不断重复上述操作，直到序列全为 0 或者出现负数。如果最终序列全为 0，说明按照这样的方式可以成功构造出一个图，也就意味着这个度数序列是可图化的；如果出现负数，说明在模拟构造图的过程中出现了矛盾（因为顶点度数不能为负），出现负数就说明上一个删掉的顶点和下一个顶点没有连接上，就不合法，也就无法构造出合法的图，即度数序列不可图化。

度序列的可图性判断过程：

关键步骤：
- 每轮操作后必须重新排序（从大到小排）
- 出现负数立即判定不可图
- 全零序列判定可图
易错点：忘记排序会导致错误判断，如四个2的序列若未排序会误判为不可图。

具体案例分析：

度数序列[3,3,2,2,1,1] ：
- 第一步：排序
  - 初始度数序列[3,3,2,2,1,1]，排序后为[3,3,2,2,1,1] 。
- 第二步：删数与减度
  - 取出最大度数d = 3，删除它，然后将接下来的 3 个数各减 1 。得到新的度数序列[2,1,1,1,1] 。
- 第三步：再次排序
  - 对[2,1,1,1,1]排序，得到[2,1,1,1,1] 。
- 第四步：删数与减度
  - 取出最大度数d = 2，删除它，将接下来的 2 个数各减 1 ，得到[0,0,1,1] 。
- 第五步：再次排序
  - 对[0,0,1,1]排序，得到[1,1,0,0] 。
- 第六步：删数与减度
  - 取出最大度数d = 1，删除它，将接下来的 1 个数减 1 ，得到[0,0,0] 。
- 第七步：判断结果
  - 最终得到全为 0 的度数序列，说明[3,3,2,2,1,1]是可图化的。
度数序列[4,4,2,1,1]：
- 第一步：排序
  - 初始度数序列[4,4,2,1,1]，排序后为[4,4,2,1,1] 。
- 第二步：删数与减度
  - 取出最大度数d = 4，删除它，然后将接下来的 4 个数各减 1 ，得到[3,1,0,0] 。
- 第三步：再次排序
  - 对[3,1,0,0]排序，得到[3,1,0,0] 。
- 第四步：删数与减度
  - 取出最大度数d = 3，删除它，将接下来的 3 个数各减 1 ，得到[0,-1,-1] 。
- 第五步：判断结果
  - 出现了负数，说明按照 Havel - Hakimi 定理的模拟构造过程出现矛盾，无法构造出合法的图，即度数序列[4,4,2,1,1]不可图化

特别说明

应用前提：使用贪心算法必须证明其能得到最优解，贪心算法是 “每一步都做当前看来最优的选择”，期望通过局部最优累积得到全局最优。但局部最优≠全局最优，所以必须证明 “贪心策略的每一步选择，都能让最终结果最优”

典型反例：

例子 1：可用贪心的货币系统（1 角、5 分、1 分）
- 要凑出13分，贪心策略是 “优先用大面值”：
- 先选1角（10分），剩余3分；
- 再选3个1分，总硬币数1 + 3 = 4。
- 这是最优解（硬币数最少）。
- 此时，“大面值尽可能多” 的贪心策略，能保证全局最优（可通过数学证明：因为 10 是 5 的倍数，5 是 1 的倍数，大面值能完全覆盖小面值的组合效率）。
例子 2：不可用贪心的货币系统（11 分、5 分、1 分）
- 要凑出15分，若用贪心（优先用大面值）：
- 先选11分，剩余4分；
- 再选4个1分，总硬币数1 + 4 = 5。
- 但更优解是选3个5分（硬币数3），比贪心结果更优。
- 此时，“大面值尽可能多” 的贪心策略失效 —— 因为 11 不是 5 的倍数，大面值无法 “高效覆盖” 小面值的组合，局部最优（选 11）导致全局非最优。
核心教训：看似自然的贪心策略可能有隐含前提条件，必须严格验证，贪心算法的 “自然直觉”（比如 “大的优先”）不一定正确，必须严格证明“每一步贪心选择都能导向全局最优”，否则可能得到错误结果。

6）例题:近点对问题

问题描述：平面上有n个点（n≤ $10^5$ ），给定所有点的坐标，求两点间的最小欧氏距离（就是最短距离）。
解题方法：
- 方法一：暴力解法
  - 思路：对每一对点都计算它们之间的欧氏距离，然后找出其中最小的距离。即通过两层嵌套循环，外层循环遍历每一个点，对于外层循环中的每一个点，内层循环遍历它后面的所有点，计算这两个点之间的距离。
  - 时间复杂度：因为需要比较每两个点，时间复杂度为 O(n2) 。当 n=105 时，计算量巨大，会超出时间限制无法通过，仅适用于 n≤1000 的小规模数据。
- 方法二：标准解法 - 分治法
  - 思路：
    - 划分：将平面上的 n 个点按照 x 坐标排序，然后把点集分成左右两个大小近似相等的子集。
    - 求解子问题：分别递归地在左子集和右子集中找出最小距离，设为 d1 和 d2，取 d=min(d1,d2)。
    - 合并：此时，“跨左右区域的最近点对” 可能存在，但只有当两点的 x 坐标距离小于 d 时，才有可能成为更优解。因此：只需要关注 “划分线附近（x 坐标与划分线差小于 d）” 的点。对这些点按 y 坐标排序后，每个点只需与下方最多 7 个点比较距离（数学可证：平面上距离小于 d 的点，在 y 有序的情况下，相邻点不会超过 7 个）
  - 时间复杂度：通过分治法，整体时间复杂度降低到 O(nlogn)，能够高效处理较大规模的数据，用 “递归 + 分治” 缩小问题规模，避免重复比较。用 “合并时的剪枝”（只比较关键的少量点），把合并阶段的时间从 O(n2) 压到 O(n)。
- 方法三：特殊解法 - 贪心策略
  - 思路：按 x+y 和排序后，仅比较相邻 7 个点。其原理是认为在这种排序下，距离最小的点对大概率会出现在相邻点中。
  - 时间复杂度：理论上比较次数减少，时间复杂度有所降低，但它存在局限性。
  - 共线时贪心策略失效：当所有点共线时，按 x+y 排序后，相邻的点不一定是距离最小的点对。因为在共线的情况下，距离最小的点对可能分散在整个点集的不同位置，而不是局限于相邻的点。
    - 例如，假设有共线的 5 个点 A,B,C,D,E ，按 x+y 排序后顺序是 A,E,B,D,C ，但距离最小的点对可能是 B 和 D ，而它们并不相邻。按照贪心策略，只比较相邻 7 个点，就可能会遗漏 B 和 D 这对距离最小的点，从而导致算法无法找到真正的最小距离，使得算法失效。而分治法在处理共线情况时，依然能按照划分、求解子问题和合并的步骤正确找到最小距离。
举个例子来更好的感受暴力法和分治法的区别
- 找班级里最矮的两个人：
  - 暴力法：让每个人和其他所有人比身高（n2 次比较）。
  - 分治法：
    - 把班级分成两组，分别找每组最矮的人（递归）。
    - 两组的 “最矮” 再比较，得到当前候选（d）。
    - 只需要检查 “两组边界附近的人”（比如身高与候选最矮的差小于 d 的人），且每个人只需和附近几个人比（剪枝）。
  - 显然，分治法的比较次数远少于暴力法。

4. 贪心算法的常见前提操作

前提操作：排序
- 贪心算法的核心是 “每一步选当前最优”，但 “当前最优” 的判断往往需要数据是有序的。比如 “选最大的数”“选结束最早的区间” 等策略，都依赖数据按特定规则（从大到小、从小到大等）排列。所以排序是贪心算法的 “前置准备”。
核心操作：排序是贪心算法的典型预处理步骤
- 很多贪心问题，第一步就是对数据排序，之后再基于有序的数据执行贪心策略。例如：
  - 区间调度问题：要选最多不重叠的区间，通常先按 “区间结束时间” 排序，然后每次选结束最早的、且不与已选区间重叠的区间。
  - 背包问题（部分背包）：按 “单位重量价值” 从大到小排序，优先选单位价值高的物品，这样能保证总价值最大。
实现方式:
- C++ 标准库sort函数（需掌握 STL）：C++ 的sort是标准模板库（STL）里的排序函数，能对数组、向量（vector）等容器进行排序，默认按 “升序” 排列（对于数值类型）。
- 对结构体 / 类对象需自定义比较函数：如果要排序的不是简单的int、double等类型，而是结构体或类的对象，需要自定义 “比较规则”。
应用场景
- 近点对问题中的坐标预处理：在 “平面最近点对” 问题中，分治法的第一步就是对 “点的坐标” 排序（按 x 或 y 坐标），这样才能高效划分区域、处理跨区域的点对。
- 区间调度、背包问题等经典贪心问题
  - 区间调度：排序后选最优区间。
  - 背包问题（部分背包）：排序后选单位价值高的物品。
  - 活动选择问题：类似区间调度，排序后选最优活动。
学习建议
- 需熟练掌握比较函数的编写：自定义比较函数是排序结构体 / 类对象的关键，要能根据问题需求，写出正确的 “排序规则”（升序、降序、多关键字排序等）。
- 注意稳定排序与非稳定排序的区别
  - 稳定排序：相等元素的相对顺序在排序后保持不变（如冒泡排序、归并排序）。
  - 非稳定排序：相等元素的相对顺序可能改变（如快速排序、C++ 的sort）。
  - 在某些问题中，元素的 “相对顺序” 很重要（比如要求相等元素按原始顺序处理），这时候要注意排序算法的稳定性。

5. 关于sort函数

1）例题:int数组排序

头文件：#include<algorithm>
参数说明：
- 必选参数：前两个参数必须提供
  - 第一个参数：要排序区间的首地址（数组名）
  - 第二个参数：区间尾地址的下一个地址（数组名+元素数量）
- 可选参数：第三个cmp函数不写时默认递增排序
半闭半开区间：排序范围包含首地址但不包含尾地址，如sort(num, num+100)表示对num数组前100个元素排序
自定义排序规则：
- 从大到小排序需要定义cmp函数：
- 使用时：sort(num, num+100, cmp)

2）例题:结构体数组排序

必要性：结构体是自定义类型，必须明确指定排序规则
多级排序：
执行特点：结构体排序时整个结构体对象会整体交换
代码优化：if条件满足时会直接return，因此可以省略else语句

3）例题:学生成绩排序

浮点数比较：
- 不能直接用==判断相等
- 正确方法：if(fabs(x.score - y.score) > 0.00001)
- 精度要求：一般取 $10^{-6}$ （针对double类型）
字符串比较：
- 字符数组使用strcmp(x.name, y.name) < 0
- string类型可直接用<运算符
三级排序示例：

4）经验之谈

常见错误：
- 当数据从下标1开始存储时，错误使用sort(num, num+100)会包含无效的num[0]
- 正确做法：sort(num+1, num+101)（假设数据存在num[1]到num[100]）
区间选择：
- 可对数组任意连续区间排序，如对前50个元素：sort(num, num+50)
- 对中间20-30元素：sort(num+20, num+31)
效率提示：
- sort函数采用优化算法，时间复杂度为O(nlog⁡n)
- 比手写排序更稳定高效，适合算法竞赛使用

算法——贪心算法