第5章：基础算法（Fundamental Algorithms）

一、导读

5.1 本章学习目标

掌握了基础数据结构之后，我们终于迎来了算法的核心地带。本章介绍算法竞赛中最基础也最重要的四类算法思想：排序、搜索、贪心和动态规划。这些算法思想不仅是竞赛的基石，更是整个计算机科学的支柱。

本章的核心学习目标包括：

掌握经典排序算法：理解快速排序、归并排序的原理和 O(n log n) 复杂度，知道何时使用何种排序。
精通二分搜索：不仅能查找元素，还能"二分答案"——当答案具有单调性时，将优化问题转化为判定问题。
理解贪心策略：学会设计贪心算法，更重要的是学会证明贪心的正确性。
建立动态规划思维：掌握状态定义、状态转移方程和边界条件这 DP 三要素。
熟悉经典 DP 模型：最长递增子序列（LIS）、背包问题等经典模型。
学会算法复杂度分析：能够分析算法的时间和空间复杂度，评估算法的效率。

5.2 为什么本章如此重要

本章的内容是算法竞赛的"半壁江山"。在绝大多数竞赛题目中，你都需要用到排序、搜索、贪心或 DP 中的至少一种。更重要的是，这些算法思想具有极强的迁移性——后续章节中的图论算法、数论算法、字符串算法，无一不是建立在这些基础思想之上。

排序是数据处理的起点。有序的数据可以进行二分搜索，可以快速去重，可以发现规律。很多看似与排序无关的问题，最终都可以转化为排序问题。

二分搜索是"减治"思想的典范。它将搜索空间每次减半，以 O(log n) 的效率令人惊叹。而"二分答案"更是竞赛中的高频考点——当你发现答案具有单调性时，二分就是最锋利的武器。

贪心和动态规划是"最优化问题"的两大武器。贪心简洁高效，但需要证明正确性；DP 通用强大，但需要设计状态。掌握这两种思想，你就能应对大量的最优化问题。

5.3 核心问题引导

在阅读本章时，请带着以下问题思考：

为什么基于比较的排序算法的下界是 O(n log n)？这个结论如何证明？

二分搜索的边界条件为什么容易出错？如何写出"永远不会错"的二分模板？

贪心算法和动态规划的本质区别是什么？什么问题能用贪心，什么问题必须用 DP？

动态规划的"无后效性"是什么意思？为什么它是 DP 成立的必要条件？

二分答案的关键是什么？如何判断一个问题是否可以二分答案？

记忆化搜索和递推式 DP 各有什么优缺点？如何选择？

二、核心概念详解

5.1 排序算法

5.1.1 快速排序

快速排序是分治策略的经典应用。选择一个"基准"（pivot），将数组分为两部分：小于基准的和大于基准的，然后递归排序两部分。

cpp

void quick_sort(int *a, int l, int r) {
    if (l >= r) return;
    int pivot = a[l + (r - l) / 2];  // 选中间元素为基准
    int i = l, j = r;
    while (i <= j) {
        while (a[i] < pivot) i++;
        while (a[j] > pivot) j--;
        if (i <= j) {
            swap(a[i], a[j]);
            i++; j--;
        }
    }
    quick_sort(a, l, j);
    quick_sort(a, i, r);
}

复杂度分析：

平均时间复杂度：O(n log n)
最坏时间复杂度：O(n²)（当数组已经有序且选首元素为基准时）
空间复杂度：O(log n)（递归栈）

5.1.2 归并排序

归并排序同样基于分治，但它的优势在于稳定且最坏情况也是 O(n log n)：

cpp

int tmp[100005];

void merge_sort(int *a, int l, int r) {
    if (r - l <= 1) return;
    int mid = l + (r - l) / 2;
    merge_sort(a, l, mid);
    merge_sort(a, mid, r);
    
    int i = l, j = mid, k = l;
    while (i < mid && j < r)
        tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
    while (i < mid) tmp[k++] = a[i++];
    while (j < r) tmp[k++] = a[j++];
    for (int i = l; i < r; i++) a[i] = tmp[i];
}

5.1.3 STL sort

竞赛中直接使用 STL 的 sort，它是 introsort（快排+堆排+插入排序的混合），性能优异：

cpp

#include <algorithm>

int a[100005];
sort(a, a + n);  // 升序排序

// 自定义比较函数
struct Point {
    int x, y;
};
bool cmp(const Point &a, const Point &b) {
    return a.x < b.x || (a.x == b.x && a.y < b.y);
}
Point pts[100005];
sort(pts, pts + n, cmp);

5.2 二分搜索

5.2.1 基本二分搜索

在有序数组中查找目标值，每次将搜索范围减半：

cpp

int binary_search(int *a, int n, int target) {
    int l = 0, r = n - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (a[mid] == target) return mid;
        else if (a[mid] < target) l = mid + 1;
        else r = mid - 1;
    }
    return -1;  // 未找到
}

关键细节：

mid = l + (r - l) / 2 而不是 (l + r) / 2，防止 l + r 溢出
循环条件是 l <= r（注意等号）
区间更新是 l = mid + 1 或 r = mid - 1（注意 ±1）

5.2.2 二分的变体

cpp

// 查找第一个 >= target 的位置（lower_bound）
int lower_bound(int *a, int n, int target) {
    int l = 0, r = n;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] < target) l = mid + 1;
        else r = mid;
    }
    return l;
}

// 查找第一个 > target 的位置（upper_bound）
int upper_bound(int *a, int n, int target) {
    int l = 0, r = n;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] <= target) l = mid + 1;
        else r = mid;
    }
    return l;
}

5.2.3 二分答案

当答案具有单调性时（即"如果 x 可行，那么 x+1 也可行"或反之），可以二分答案：

cpp

// 模板：最小化最大值
bool check(int mid);  // 验证 mid 是否可行

int binary_answer(int l, int r) {
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (check(mid)) r = mid;     // mid 可行，尝试更小的
        else l = mid + 1;            // mid 不可行，必须更大
    }
    return l;
}

经典应用：将 n 本书分给 k 个抄写员，使最大工作量最小化。

5.3 贪心算法

5.3.1 贪心的本质

贪心算法在每一步都选择局部最优解，期望通过局部最优达到全局最优。贪心算法的关键在于正确性证明——不是所有问题都能用贪心。

5.3.2 活动选择问题

问题：有 n 个活动，每个活动有开始时间 sᵢ 和结束时间 fᵢ，求最多能参加多少个活动（活动时间不能重叠）。

贪心策略：每次选择结束时间最早的、与已选活动不冲突的活动。

cpp

#include <cstdio>
#include <algorithm>
using namespace std;

struct Activity {
    int s, f;
    bool operator<(const Activity &o) const {
        return f < o.f;  // 按结束时间排序
    }
};

Activity a[100005];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d%d", &a[i].s, &a[i].f);
    
    sort(a, a + n);
    
    int cnt = 1, last_end = a[0].f;
    for (int i = 1; i < n; i++) {
        if (a[i].s >= last_end) {
            cnt++;
            last_end = a[i].f;
        }
    }
    printf("%d\n", cnt);
    return 0;
}

正确性证明（交换论证）：假设最优解的第一个活动不是结束最早的，那么可以将其替换为结束最早的活动，不会使解变差。以此类推，贪心解不劣于最优解。

5.3.3 贪心 vs DP

特征	贪心	动态规划
决策方式	每步选局部最优	枚举所有可能的决策
正确性	需要证明	天然正确（穷举）
效率	通常 O(n log n)	通常 O(n²) 或 O(n³)
适用范围	具有贪心选择性质	具有最优子结构和重叠子问题

5.4 动态规划

5.4.1 DP 的三要素

动态规划的核心在于三个要素：

状态定义：dp[i] 或 dp[i][j] 代表什么含义？

状态转移方程：dp[i] 如何从之前的状态推导出来？

边界条件：最小的子问题的答案是什么？

5.4.2 最长递增子序列（LIS）

问题：给定序列 a[1..n]，求最长的严格递增子序列的长度。

O(n²) 解法：

cpp

int a[1005], dp[1005];
int n;

// dp[i] = 以 a[i] 结尾的 LIS 长度
int lis() {
    int ans = 0;
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i])
                dp[i] = max(dp[i], dp[j] + 1);
        }
        ans = max(ans, dp[i]);
    }
    return ans;
}

O(n log n) 解法：使用二分优化。

cpp

#include <algorithm>
#include <vector>

int lis_fast(int *a, int n) {
    vector<int> tails;  // tails[i] = 长度为 i+1 的递增子序列的最小末尾
    for (int i = 0; i < n; i++) {
        auto it = lower_bound(tails.begin(), tails.end(), a[i]);
        if (it == tails.end())
            tails.push_back(a[i]);
        else
            *it = a[i];
    }
    return tails.size();
}

5.4.3 0-1 背包问题

问题：n 个物品，每个有重量 wᵢ 和价值 vᵢ，背包容量 W。每个物品要么选要么不选，求最大总价值。

cpp

int w[105], v[105];
int dp[1005];  // dp[j] = 容量为 j 时的最大价值
int n, W;

int knapsack() {
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < n; i++) {
        for (int j = W; j >= w[i]; j--) {  // 逆序遍历，保证每个物品只选一次
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    return dp[W];
}

关键细节：内层循环必须逆序遍历。如果正序遍历，同一个物品会被选多次（变成完全背包问题）。

三、实战案例

3.1 案例一：二分答案——木材加工

问题描述：有 n 根木材，长度分别为 Lᵢ。需要切割出 k 根等长的木材，求最大长度。

cpp

#include <cstdio>
#include <algorithm>
using namespace std;

int L[100005], n, k;

bool check(int len) {
    int cnt = 0;
    for (int i = 0; i < n; i++)
        cnt += L[i] / len;
    return cnt >= k;
}

int main() {
    scanf("%d%d", &n, &k);
    int max_L = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &L[i]);
        max_L = max(max_L, L[i]);
    }
    
    int l = 1, r = max_L;
    while (l < r) {
        int mid = l + (r - l + 1) / 2;  // 注意 +1
        if (check(mid)) l = mid;         // mid 可行，尝试更大
        else r = mid - 1;                // mid 不可行，必须更小
    }
    printf("%d\n", l);
    return 0;
}

3.2 案例二：DP——数字三角形（递推版）

cpp

#include <cstdio>
#include <algorithm>
using namespace std;

int a[105][105], dp[105][105];
int n;

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j <= i; j++)
            scanf("%d", &a[i][j]);
    
    dp[0][0] = a[0][0];
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            dp[i][j] = a[i][j];
            if (j > 0) dp[i][j] = max(dp[i][j], dp[i-1][j-1] + a[i][j]);
            if (j < i) dp[i][j] = max(dp[i][j], dp[i-1][j] + a[i][j]);
        }
    }
    
    int ans = 0;
    for (int j = 0; j < n; j++)
        ans = max(ans, dp[n-1][j]);
    printf("%d\n", ans);
    return 0;
}

四、本章小结

本章系统介绍了四类基础算法：

排序：快速排序和归并排序是 O(n log n) 的代表，竞赛中直接使用 STL sort。

二分搜索：不仅用于查找，还能"二分答案"——将优化问题转化为判定问题。

贪心：每步选局部最优，关键在于正确性证明。活动选择是经典贪心问题。

动态规划：状态定义、状态转移、边界条件是 DP 三要素。LIS 和背包是经典模型。

这四种算法思想不是孤立的——排序为二分创造条件，二分可以优化 DP，贪心是 DP 的特殊情况。理解它们之间的联系，才能在竞赛中灵活运用。

五、思考与练习

思考题

快速排序的最坏情况是什么？如何避免？为什么 STL sort 不会出现最坏情况？

二分搜索中 l <= r 和 l < r 的区别是什么？对应的区间更新有什么不同？

如何证明一个贪心策略是正确的？"交换论证"的核心思想是什么？

动态规划中的"无后效性"是什么意思？举例说明什么情况下不满足无后效性。

编程练习

归并排序求逆序对：利用归并排序的过程，统计数组中逆序对的数量。

最大化最小值：n 个牛栏排成一行，放入 k 头牛，使相邻牛的最小距离最大。

完全背包：每种物品可以选无限次，求最大价值。

最长公共子序列（LCS）：求两个序列的最长公共子序列长度。