算法总结篇（枚举-分治）

双指针 O(n)

寻找满足特定条件的连续子区间。

• “唯一的雪花” (UVA11572)：寻找最长的、所有元素互不相同的连续子数组。
• “逛画展” (P1638)：寻找最短的、包含了所有不同元素（画家）​ 的连续子数组。
• “字符串”：寻找最短的、包含了所有小写字母的连续子串。

同向双指针维护一个共同的滑动窗口。

• 右指针已右移，有新元素纳入窗口，要更新窗口状态信息。
• 满足特定窗口条件时，左指针要收缩，并更新窗口信息。
• 右指针右移

left和 right都只向右移动，永不回退。状态维护依赖哈希表。将复杂度O(n^2)将至O(n)。总结来说，当你遇到一道算法题，并且它符合“在序列上寻找一个满足某全局条件的最优连续子区间”这一模型时，就应优先考虑双指针（滑动窗口）算法。解题框架固定：用左右指针表示窗口，右扩左缩，用哈希表维护窗口状态，在窗口合法时更新答案。​

二分 O(n*logn）

二分查找模板-CSDN博客

二分的两大模型：1. 有序序列上的位置二分 2. 答案空间上的判定二分（二分答案）

二分的核心不是“找中点”，而是“找到一个具有单调性的判定对象”。

1. 都能抽象成“二段性”。前一段不满足，后一段满足；或前一段满足，后一段不满足。

• 例如：
  • 跳石头：允许的最短跳跃距离 d 越小，越容易满足条件
  • 砍树：锯的高度 h 越低，得到的木材越多
  • 木材加工：长度 len 越小，能切出的段数越多
  • 木材加工：长度 len 越小，能切出的段数越多

也就是说，这类题都存在一个“分界点”。

2. 二分的对象不一定是数组下标，也可能是答案

• 这几题正好覆盖了二分的两大类型：
  • A-B数对、烦恼的高考志愿：二分的是“有序数组中的位置”
  • 木材加工、砍树、跳石头：二分的是“答案本身”

这说明二分题最重要的不是数组，而是：是否有范围，是否有单调性，是否能判断当前值行不行。

3. 二分答案题基本都在求最值

• 木材加工：求最大可行长度
• 砍树：求最大可行高度
• 跳石头：求最大可行的最短跳跃距离

所以二分答案题常见信号就是：

• 最大化最小值
• 最小化最大值
• 求最大可行值
• 求最小满足值

只要题目问的是“最优值”， 并且可以转成“这个值是否可行”，就很像二分答案。

4.判定函数check()比求解过程更重要

• 在这些题里，真正决定能不能二分的，不是模板，而是判定逻辑：
  • 木材加工：check(len) = 能否切出至少 k 段
  • 砍树：check(h) = 砍完后木材总量是否至少为 m
  • 跳石头：check(d) = 是否能在移除不超过 m 块石头的前提下，让每一步都至少跳 d

这类题的特点是，正着求答案难，但反过来验证一个答案是否成立很容易。这是二分答案很典型的特征。

二分成立的必要条件：

1. 搜索空间能否有一个明确区间
2. 对区间中的某个值，能否快速判断“是否可行”
3. 判定结果具有单调性

5.依赖边界处理

• 典型边界包括：
  • 目标比所有数都小/都大
  • 答案可能不存在
  • mid取上中还是下中位数
  • 是否需要补0，终点，哨兵
• 比如：
  • 烦恼的高考志愿 要先判断是否落在整体区间外
  • 木材加工 最后还要检查一次是否真的可行，否则输出 0
  • 跳石头 往往要把起点 0 和终点 L 也纳入考虑

所以二分题非常考验“边界意识”。

6.二分题的本质是“有序性”，这个有序性可以来自数组本身，也可以来自答案天然有序

• 查找型二分通常先排序
• 答案型二分通常不一定排序答案，但要让“判定结果”具备单调性

例如：

• A-B数对、烦恼的高考志愿：数组排序后才能二分查找
• 跳石头：石头位置天然有序，或者需要排序后处理间距
• 木材加工、砍树：虽然不一定需要排序木头本身，但答案区间是有序的

7. 二分的复杂度本质

二分为什么强，不只是因为“会模板”， 而是因为它把搜索规模从线性压到对数级。二分的复杂度本质是：每次排除一半区间，因此总复杂度通常是 O(log n) 或 O(log V)，结合判定函数，则总复杂度常为 O(check * log V)。

贪心的题目比较难总结，写的题目还是偏少。

贪心：货仓选址_c++ p10452 货仓选址-CSDN博客

这是一道经典的贪心题目。

贪心：拼数-CSDN博客

贪心：保卫花园-CSDN博客

• 在确定好 (假设贪心 O(n*logn) / O(logn) 确定好) 顺序的序列中，拿出相邻的两个元素
• 如果交换这两个元素，对前面以及后面确定好顺序的序列的结果不造成影响
• 此时就可以根据这两个元素交换前后的结果，推导出排序的规则

贪心：哈夫曼编码-CSDN博客

基于堆的贪心 O(log⁡n)

贪心：线段覆盖-CSDN博客

这是一道我认为很经典的区间取舍题目。

贪心：Stall Reservations S（重写）-CSDN博客

这道题有点像区间覆盖，但是，这道题是区间覆盖的升级。对于重复的区间，我们要另开一段。产奶起始时间相当于比赛开始时间，产奶结束时间相当于比赛结束时间。

数组按起始时间升序排序，优先级队列按结束时间升序排序。最快开始时间匹配最快结束时间，如果最快结束时间晚于最快开始时间，说明要另请牛棚。否则，分配该牛棚的编号，更新结束时间重新入队。

贪心：Sunscreen G-CSDN博客

有多种可执行方案，举出可执行方案的反例。

贪心首先要做排序，题目如果给定一个对象两个值的话，可以使用结构体。

离散化

离散化：贴海报-CSDN博客

排序+去重+二分+差分+前缀和+计算结果