分治CSP-J

💡 核心思想

分治（Divide and Conquer）的核心思想是：将问题分成若干个规模更小的子问题，递归地求解子问题，再将子问题的解合并为原问题的解。三个步骤：分解（Divide）、解决（Conquer）、合并（Combine）。

🎯 直觉理解

想象你要数一堆硬币的总金额。你把硬币分成两堆，分别数出每堆的金额，然后加起来。每堆还可以继续分成更小的堆……直到一堆只有一个硬币（直接知道金额）。这就是分治。

📝 算法流程

1. 分解：将原问题分为 k 个规模更小的子问题
2. 解决：递归求解各子问题（若足够小则直接求解）
3. 合并：将子问题的解合并为原问题的解

$$T(n) = aT(n/b) + O(n^d) \text{（主定理通用形式）}$$

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
// 归并排序 - 分治经典应用
void mergeSort(vector<int>& a, int l, int r) {
    if (l >= r) return;                // 一个元素，已经有序
    int mid = (l + r) / 2;
    mergeSort(a, l, mid);             // 排左半
    mergeSort(a, mid + 1, r);         // 排右半
    // 合并两个有序数组
    vector<int> tmp;
    int i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) tmp.push_back(a[i++]);
        else tmp.push_back(a[j++]);
    }
    while (i <= mid) tmp.push_back(a[i++]);
    while (j <= r) tmp.push_back(a[j++]);
    for (int k = 0; k < tmp.size(); k++)
        a[l + k] = tmp[k];
}
int main() {
    int n; cin >> n;
    vector<int> a(n);
    for (auto& x : a) cin >> x;
    mergeSort(a, 0, n - 1);
    for (auto x : a) cout << x << ' ';
    return 0;
}

⚠️ 常见坑点

📚 相关题目