【算法】分治
分治
- 1.逆序对
- 2.求第 k 小的数
- 3.最大子段和
- 4.地毯填补问题
分治，字面上的解释是「分而治之」，就是把一个复杂的问题分成两个或更多的相同的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
1.逆序对
P1908 逆序对
解法：分治
「分治」是解决「逆序对」⾮常经典的解法，也可以利用「树状数组」或「线段树」解决逆序对问题。
如果把整个序列 [l, r] 从中间 mid 位置分成两部分，那么逆序对个数可以分成三部分：
- [l, mid] 区间内逆序对的个数 c1。
- [mid + 1, r] 区间内逆序对的个数 c2。
- 从 [l, mid] 以及 [mid + 1, r] 各选一个数，能组成的逆序对的个数 c3。
那么逆序对的总数就是 c1 + c2 + c3。其中求解 c1，c2的时候跟原问题是一样的，可以交给「递归」去处理，那我们重点处理「一左一右」的情况。
如果在处理一左一右的情况时，两个数组「无序」，我们的时间复杂度其实并没有优化到哪去，甚至还「不如暴力解法」。但是如果两个数组有序的话，我们就可以快速找出逆序对的个数。
先不管怎么求逆序对，我们能让左右两个数组有序嘛？就是「归并排序」。因此，我们能做到在求完 c1, c2 之后，然后让「左右两个区间有序」。那么接下来问题就变成，已知两个「有序数组」，如何求出左边选一个数，右边选一个数的情况下的逆序对的个数。核心思想就是找到右边选一个数之后，左边区间内「有多少个比我大的」。
定义两个「指针」扫描两个有序数组，此时会有下面三种情况：
- a[cur1] ≤ a[cur2]：a[cur1] 不会与 [cur2, r] 区间内任何一个元素构成逆序对，cur1++。
- a[cur1] > a[cur2]：此时 [cur1, mid] 区间内所有元素都会与 a[cur2] 构成逆序对，逆序对个数增加，mid − cur1 + 1，此时 cur2 已经统计过逆序对了，cur2++。
重复上面两步，我们就可以在 O(N) 的时间内处理完「一左一右」时，逆序对的个数。而且，我们会发现，这跟我们「归并排序的过程」是高度一致的。所以可以一边排序，一边计算逆序对的个数。
#include<iostream>
using namespace std;
typedef long long LL;
const int N = 5e5 + 10;
int n;
int a[N];
int t[N]; //辅助数组
LL merge(int left, int right)
{
if(left == right) return 0;
LL ret = 0;
int mid = (left + right) / 2;
ret += merge(left, mid);
ret += merge(mid + 1, right);
//一左一右的情况
int cur1 = left, cur2 = mid + 1, i = left;
while(cur1 <= mid && cur2 <= right)
{
if(a[cur1] <= a[cur2]) t[i++] = a[cur1++];
else
{
ret += mid - cur1 + 1;
t[i++] = a[cur2++];
}
}
while(cur1 <= mid) t[i++] = a[cur1++];
while(cur2 <= right) t[i++] = a[cur2++];
for(int j = left; j <= right; j++) a[j] = t[j];
return ret;
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
cout << merge(1, n) << endl;
return 0;
}
2.求第 k 小的数
P1923 【深基9.例4】求第 k 小的数
解法：分治
在快排中，当我们把数组「分成三块」之后： [l, left] [left + 1, right - 1] [right, r] ，我们可以通过计算每一个区间内元素的「个数」，进而推断出我们要找的元素是在「哪一个区间」里面。
那么我们可以直接去「相应的区间」去寻找最终结果就好了。
#include<iostream>
#include<ctime>
using namespace std;
const int N = 5e6 + 10;
int n, k;
int a[N];
int GetRandom(int left, int right)
{
return a[rand() % (right - left + 1) + left];
}
int QuickSelect(int left, int right, int k)
{
if(left == right) return a[left];
//1.随机选择基准值
int key = GetRandom(left, right);
//2.数组分三块
int l = left - 1, r = right + 1, cur = left;
while(cur < r)
{
if(a[cur] < key) swap(a[++l], a[cur++]);
else if(a[cur] == key) cur++;
else swap(a[cur], a[--r]);
}
//3.选择存在最终结果的区间
//[left, l] [l + 1, r - 1] [r, right]
int a = l - left + 1, b = r - 1 - l, c = right - r + 1;
if(k <= a) return QuickSelect(left, l, k);
else if(k <= a + b) return key;
else return QuickSelect(r, right, k - a - b);
}
int main()
{
srand(time(0));
scanf("%d%d", &n, &k);
k++;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]); //cin、cout超时
cout << QuickSelect(1, n, k) << endl;
return 0;
}
3.最大子段和
P1115 最大子段和
解法：分治
如果把整个序列 [l, r] 从中间 mid 位置分成两部分，那么整个序列中「所有的子数组」就分成三部分：
- 子数组在区间 [l, mid] 内。
- 子数组在区间 [mid + 1, r] 内。
- 子数组的左端点在 [l, mid] 内，右端点在 [mid + 1, r] 内。
那么我们的「最终结果」也会在这三部分取到，要么在左边区间，要么在右边区间，要么在跨越中轴线的区间。因此，我们可以先求出左边区间的最大子段和，再求出右边区间的最大子段和，最后求出中间区间的最大子段和。其中求「左右区间」时，可以交给「递归」去解决。
那我们重点处理如何求出「中间区间」的最大子段和。可以把中间区间分成两部分：
- 左边部分是从 mid 为起点，「向左延伸」的最大子段和。
- 右边部分是从 mid + 1 为起点，「向右延伸」的最大子段和。
分别求出这两个值，然后相加即可。求法也很简单，直接「固定起点」，一直把「以它为起点的所有子数组」的和都计算出来，取最大值即可。
#include<iostream>
using namespace std;
const int N = 2e5 + 10;
int n;
int a[N];
int dfs(int left, int right)
{
if(left == right) return a[left];
int mid = (left + right) / 2;
//先求出左右两边的最大值
int ret = max(dfs(left, mid), dfs(mid + 1, right));
//求出以a[mid]开始，向左延伸的最大值
int sum = a[mid], lmax = a[mid];
for(int i = mid - 1; i >= left; i--)
{
sum += a[i];
lmax = max(lmax, sum);
}
//求出以a[mid+1]开始，向右延伸的最大值
sum = a[mid + 1]; int rmax = a[mid + 1];
for(int i = mid + 2; i <= right; i++)
{
sum += a[i];
rmax = max(rmax, sum);
}
//求三者的最大值
ret = max(ret, lmax + rmax);
return ret;
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
cout << dfs(1, n) << endl;
return 0;
}
4.地毯填补问题
P1228 地毯填补问题
解法：分治
非常经典的一道分治题目，也可以说是一道递归题目。
一维分治的时候，我们是从中间把整个区间切开，分成左右两部分（其实有时候我们可以三等分，就看具体问题是什么）。⼆维的时候，我们可以横着一刀竖着一刀，分成左上、右上、左下、右下四份。而这道题的矩阵长度正好是 2^k，能够被不断平分下去。像是在暗示我们，要用分治，要用分治，要用分治…
当我们把整个区间按照中心点一分为四后，四个区间里面必然有一个区间有缺口（就是公主的位置），那这四个区间不一样，那就没有相同子问题了。别担心，只要我们在中心位置放上一块地毯，四个区间就都有一个缺口了。如下图所示：
无论缺口在哪里，我们都可以在缺口对应的区间的角落，放上一个地毯。接下来四个区间都变成只有一个缺口的形式，就可以用递归处理子问题。因此，我们拿到一个矩阵后的策略就是：
- 先四等分。
- 找出缺口对面的区间，放上一块地毯。
- 递归处理四个子问题。
#include<iostream>
using namespace std;
int k, x, y;
//len: 区间的长度; (a, b): 区间的左上角坐标; (x, y): 障碍物的坐标
void dfs(int len, int a, int b, int x, int y)
{
if(len == 1) return;
len /= 2;
if(x < a + len && y < b + len) //障碍物在左上角
{
cout << a + len << " " << b + len << " " << 1 << endl; //铺上1号地毯
dfs(len, a, b, x, y);
dfs(len, a, b + len, a + len - 1, b + len);
dfs(len, a + len, b, a + len, b + len - 1);
dfs(len, a + len, b + len, a + len, b + len);
}
else if(x >= a + len && y >= b + len) //障碍物在右下角
{
cout << a + len - 1 << " " << b + len - 1 << " " << 4 << endl; //铺上4号地毯
dfs(len, a, b, a + len - 1, b + len - 1);
dfs(len, a, b + len, a + len - 1, b + len);
dfs(len, a + len, b, a + len, b + len - 1);
dfs(len, a + len, b + len, x, y);
}
else if(x >= a + len) //障碍物在左下角
{
cout << a + len - 1 << " " << b + len << " " << 3 << endl; //铺上3号地毯
dfs(len, a, b, a + len - 1, b + len - 1);
dfs(len, a, b + len, a + len - 1, b + len);
dfs(len, a + len, b, x, y);
dfs(len, a + len, b + len, a + len, b + len);
}
else //障碍物在右上角
{
cout << a + len << " " << b + len - 1 << " " << 2 << endl; //铺上2号地毯
dfs(len, a, b, a + len - 1, b + len - 1);
dfs(len, a, b + len, x, y);
dfs(len, a + len, b, a + len, b + len - 1);
dfs(len, a + len, b + len, a + len, b + len);
}
}
int main()
{
cin >> k >> x >> y;
k = (1 << k);
dfs(k, 1, 1, x, y);
return 0;
}