分治算法

本文代码适用于c++

引入

现在来了一队女生共n人，但是我们得知其中有一位是小南娘。我们如何快速找到那位小南娘呢？

每次查询一个队列我们可以得到该队列中是否存在南娘。

不难想到，我们可以将这n人均分成两组，然后再将含有小南娘的那一组继续均分......直到最小的组只有一人。这样时间复杂度为O(log n)。

在解决上面查小南娘的问题中我们正是使用了分治的思想。分治算法的要点在于【拆】：如何将问题拆分为小问题;【合】：将小问题的解合并为最终问题的解。

下面我们看几个典型的例子。

归并排序

给定一个数列a，将它排序。

分析

考虑如何【拆】【合】

1. 【拆】:不难想到，只需将数列分成几个小数列分别排序即可。当数列只有一元时它就天然有序。
2. 【合】：如何将两个有序的数列合并成一个有序的数列呢？我们可以用双指针轻松解决

双指针即定义两个指针i，j。
对于两个有序数列a，b:
（不妨两者都是从小到大）
初始令i=j=1（i，j分别用来访问a，b）
每次操作将ai，bj中较小的一项加入数列c，并且让最小一项对应的指针加一。
这样经过|a|+|b|次操作，我们就可以将两个有序数列合并为新的有序数列

代码实现

#include <iostream>
#include <cstdio>
using namespace std;long long n, cnt = 0;
long long a[500005];
long long tmp[500005];void merge(int l, int mid, int r)
{int i = l, j = mid + 1, k = l;while (i <= mid && j <= r){if (a[i] <= a[j]){tmp[k++] = a[i++];}else{tmp[k++] = a[j++];}}while (i <= mid) tmp[k++] = a[i++];while (j <= r) tmp[k++] = a[j++];for (int m = l; m <= r; m++) a[m] = tmp[m];
}void doit(int l, int r)
{if (l >= r) return; // 递归终止条件（单个元素无需排序）int mid = (l + r) / 2;doit(l, mid);       // 排序左子数组（l~mid）doit(mid + 1, r);   // 排序右子数组（mid+1~r）merge(l, mid, r);   // 合并两个有序子数组
}int main()
{cin >> n;for (int i = 1; i <= n; i++){scanf("%lld", &a[i]);}doit(1, n);for (int i = 1; i <= n; i++) {cout << a[i] << " ";}return 0;
}

逆序对

问题

给定数列a，求满足i>j，ai<aj的（i,j）个数。

分析

1. 【拆】 [l,r]拆分为[l,mid]和[mid+1,r]。当区间长度为1时没有逆序对。
2. 【合】 [l,r]中的逆序对无非三种：
   (1) i，j都在[l,mid]中
   (2) i, j都在[mid+1,r]中
   (3) i，j分别在两个区间中

问题在于如何求解（3）类中的逆序对个数。

由于每个子区间中的逆序对个数已经确定，其内部的序已经不重要，我们可以将子区间内部进行排序，然后通过双指针的方法解决。

代码实现

#include <iostream>
#include <cstdio>
using namespace std;long long n, cnt = 0;
long long a[500005];
long long tmp[500005];void merge(int l, int mid, int r)
{int i = l, j = mid + 1, k = l;while (i <= mid && j <= r){if (a[i] <= a[j]){tmp[k++] = a[i++];}else{// 左子数组剩余元素都与a[j]构成逆序对cnt += mid - i + 1;tmp[k++] = a[j++];}}while (i <= mid) tmp[k++] = a[i++];while (j <= r) tmp[k++] = a[j++];for (int m = l; m <= r; m++) a[m] = tmp[m];
}void doit(int l, int r)
{if (l >= r) return; // 递归终止条件（单个元素无需排序）int mid = (l + r) / 2;doit(l, mid);       // 排序左子数组（l~mid）doit(mid + 1, r);   // 排序右子数组（mid+1~r）merge(l, mid, r);   // 合并两个有序子数组
}int main()
{cin >> n;for (int i = 1; i <= n; i++){scanf("%lld", &a[i]);}doit(1, n);cout << cnt << endl; // 可选：输出逆序对数量
//	for (int i = 1; i <= n; i++) {
//		cout << a[i] << " ";
//	}return 0;
}