首页 > 编程笔记 > C++笔记 阅读：63

C++分治算法的使用（附带实例）

分治法（Divide and Conquer）是一种递归算法设计技术，其基本思想是将一个难以直接解决的大问题分解成若干规模较小且形式相同的子问题，逐一解决这些子问题，然后将这些子问题的解决结果合并以得到原问题的答案。

分治法通常包含以下三个步骤：

分治法的优劣势

1) 分治法的优势

2) 分治法的劣势


例如，对于问题，其问题域为区间 [l,r]，如果问题具有分治特征，可以计算一个中间值 mid，分别处理 [l,mid] 和 [mid+1,r]，然后通过某种方式将两个子问题的结果，从而得到整个问题的解。

举例来说，假如要求区间 [l,r] 的元素之和，可以将其划分为 [l,mid] 和 [mid+1,r] 两个区间的和，然后将两部分结果相加，这种思想在线段树中也被广泛应用。

分治法一般采用递归的方式实现，因此需要注意递归出口和递归层数等问题。

分治法常见的题目有：最大子段和、归并排序（同时可以用来计算逆序对）、二分搜索、快速幂等。分治法经常作为一种核心思想嵌入其他算法或数据结构中，因此单独对分治法进行考察没有太大意义。

【实例 1】 StarryCoding P24最大子段和。给定一个长度为 n 的数组 a，求最大连续子段和（子段长度至少为 1）。
输入格式：
输出格式：
样例输入：

5
1 2 -4 4 5

样例输出：

9

最大子段和为 a4+a5=9。

样例输入：

6
-1 -2 -3 -5 -2 -3

样例输出：

-1


解题思路：对于区间 [l,r] 内的子段，假设左右端点分别为 x、y，中间点为 mid，可以分为三类：
当 l=r 时，直接返回 a[l] 即可，需要注意的是，子段和可能为负数，因此左侧最大后缀和、右侧最大前缀和的初始值应分别设为 a[mid] 和 a[mid+1]。 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 9;
ll a[N];

// 定义一个函数 f，用于计算区间 [l, r] 内的最大子段和
ll f(int l, int r) {
    // 如果区间只有一个元素，则直接返回该元素值
    if (l == r) return a[l];
    // 计算区间的中间位置
    int mid = (l + r) >> 1;
    // 初始化左右两侧的最大子段和为中间位置的元素值
    ll mxL = a[mid], mxR = a[mid + 1];
    // 初始化左侧子段和为 0
    ll sum = 0;
    // 从中间位置向左遍历，计算最大子段和
    for (int i = mid; i >= l; --i)
        sum += a[i], mxL = max(mxL, sum);
    // 重置左侧子段和为 0
    sum = 0;
    // 从中间位置向右遍历，计算最大子段和
    for (int i = mid + 1; i <= r; ++i)
        sum += a[i], mxR = max(mxR, sum);
    // 返回三种情况的最大值：左侧最大子段和加上右侧最大子段和、左半部分的最大子段和、右半部分的最大子段和
    return max({mxL + mxR, f(l, mid), f(mid + 1, r)});
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n; cin >> n;
    // 输入数组元素
    for (int i = 1; i <= n; ++i) cin >> a[i];
    // 输出整个数组的最大子段和
    cout << f(1, n) << '\n';
    return 0;
}

【实例 2】 StarryCoding P54 模板排序。给定一个大小为 n 的整型数组 a，需要对其按照升序排序并去重。
输入格式：
输出格式：
样例输入：

8
2 0 2 3 0 7 1 7

样例输出：

0 1 2 3 7


本题可采用归并排序来求解：
为了简化和提高可读性，我们使用 vector 容器来实现。以下为示例程序的代码： 
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 9;
// 定义常量N，表示数组的最大长度
using ll = long long;
// 定义长整型别名ll
ll a[N];
// 定义一个长整型数组a，用于存储输入的数据
// 归并排序函数，参数l和r分别表示待排序数组的左边界和右边界
vector<ll> merge_sort(int l, int r)
{
    if (l == r) return vector<ll>(1, a[l]); // 如果左右边界相等，则说明只有一个元素，直接返回该元素的向量
    int mid = (l + r) >> 1; // 计算中间位置
    vector<ll> vl = merge_sort(l, mid); // 递归调用归并排序处理左半部分
    vector<ll> vr = merge_sort(mid + 1, r); // 递归调用归并排序处理右半部分
    int pl = 0, pr = 0; // 初始化两个指针pl和pr，分别指向vl和vr的起始位置
    vector<ll> res; // 定义结果向量res
    while (res.size() < r - l + 1) // 当结果向量的大小小于待排序区间的长度时，继续合并
    {
        if (pl == vl.size()) res.push_back(vr[pr++]); // 如果pl已经到达vl的末尾，则将vr中的元素加入res
        else if (pr == vr.size()) res.push_back(vl[pl++]); // 如果pr已经到达vr的末尾，则将vl中的元素加入res
        else if (vl[pl] < vr[pr]) res.push_back(vl[pl++]); // 如果vl当前元素小于vr当前元素，则将vl当前元素加入res
        else res.push_back(vr[pr++]); // 否则，将vr当前元素加入res
    }
    return res; // 返回合并后的有序向量
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 优化输入/输出流
    int n; cin >> n; // 输入数组长度n
    for (int i = 1; i <= n; ++i) cin >> a[i]; // 输入数组元素
    vector<ll> res = merge_sort(1, n); // 对数组进行归并排序
    res.erase(unique(res.begin(), res.end()), res.end()); // 去除重复元素
    for (int i = 0; i < res.size(); ++i) cout << res[i] << ' '; // 输出排序后的结果
    return 0;
}

相关文章