红魔咖啡馆

头发越掉越多，头发越掉越少

0%

【算法】分治

发表于 分类于 ，
本文字数： 4.4k 阅读时长 ≈ 8 分钟
介绍了分治的原理与应用

分治

​ 即将整个问题分为若干个小问题后分而治之，最后逐步合并子问题的解以找到最终解

​ 分治算法是一种找大规模问题与小规模问题关系的方法，故用递归来表示

实例：归并排序

归并排序是依靠将数组分为若干小数组分别排序，最后合并得到结果的方法实现排序的

步骤如下：

  1. 将数组分为两部分
  2. 递归分别将两个子数组排序
  3. 合并两子序列

时间复杂度：\(O(n\log n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
using namespace std;

    int a[100001], temp[100001];
    /*
    步骤：
    1.将数列划为两部分
    2.递归地分别对两个子序列归并排序
    3.合并两个子序列
    */
   // 时间复杂度：O(nlogn)
void merge_sort(int l, int r){
    // 只有一个元素
    if (l == r) return ;
    // 将数组分为[l,mid] [mid+1,r] 使用>>1 相当于/2 速度更快
    int mid = (l+r) >> 1;
    // 分数组并分别进行排序
    merge_sort(l, mid);
    merge_sort(mid+1, r);
    // 合并
    int i = l, j = mid+1, k = l;
    // 当两部分数组都还有数
    while (i<=mid && j<=r){
        // 把小的加入数组tmp
        if (a[i] <= a[j]) temp[k++]=a[i++];
        else temp[k++]=a[j++];
    }
    // 两部分数组有一部分剩余的情况下，将剩余的一个个放到tmp中
    while (i<=mid){
        temp[k++]=a[i++];
    }
    while (j<=r){
        temp[k++]=a[j++];
    }
    // tmp拷贝到原数组
    for (int i = 1; i<=r; ++i) a[i] = temp[i];
}
int main(){
    int n ;
    scanf("%d", &n);
    for (int i = i ; i <=n; ++i) scanf("%d", &a[i]);
    merge_sort(1,n);
    for (size_t i = 1; i <= n; i++)
    {
        if (i == n) printf("%d\n", a[i]);
        else printf("%d", a[i]);
    }
    return 0;
    
}

最大子数组问题

输入：数组a[1…n]

输出：(i,j,s)使得a[i…j]为最大子数组，且和为s

分治策略

  • 分：取中点：最大子数组要不完全在左侧要不完全在右侧或者跨越重点
  • 治：完全位于某一侧可以递归解决；跨越中点可以从终点向两侧扩张遍历解决
  • 合：三种情况和取最大即可

时间复杂度：\(O(n\log n)\)

对于跨越中点的子数组：

image-20241212214202467

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// 使用分治求最大子段和
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <utility>
#include <cstring>
#include <iomanip>
#include <cmath>
#include <climits>
#define ios ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'
using namespace std;
using ll = long long;
const int N = 2e5+10;
int n;
int arr[N];
// 寻找贯穿左右数列的数列的最大值
// 核心思路：从中点往两边寻找，分别找左右最大相加即可
int findcrossmax(int l, int r, int mid){
  int sum=0;
  int left_big = INT_MIN; // 初始化要足够小，因为有负数最小为-1e4
  for(int i = mid; i>=l;i--){ // 中间往左寻找
    sum+=arr[i]; // 一个个求和
    if (sum>left_big) left_big = sum; // 寻找最大左段和
  }
  sum=0;
  int right_big = INT_MIN;
  for(int i = mid+1; i<=r;i++){ // 中间往右寻找
    sum+=arr[i]; // 一个个求和
    if (sum>right_big) right_big = sum; // 寻找最大右段和
  }
  return left_big+right_big; // 返回最大两段和

}
// 寻找最大值
int findmax(int l, int r){
  if (l==r) return arr[l]; // 分段达到最小，返回值
  int mid = l+r>>1; // 选择中间值
  int left_big = findmax(l,mid); // 递归寻找左端最大值
  int right_big = findmax(mid+1,r); // 递归寻找右端最大值
  int cross_big = findcrossmax(l,r,mid); // 寻找中段最大值
  return max(cross_big, max(left_big,right_big)); // 返回三者最大值
}
int main(){
  cin >> n;
  for (int i =1;i<=n;i++) cin >> arr[i];
  cout << findmax(1,n);
  return 0;
}

求逆序对

题目描述

猫猫 TOM 和小老鼠 JERRY 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。

最近，TOM 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中 \(a_i>a_j\) 且 \(i<j\) 的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。

输入格式

第一行，一个数 \(n\)，表示序列中有 \(n\) 个数。

第二行 \(n\) 个数，表示给定的序列。序列中每个数字不超过 \(10^9\)。

输出格式

输出序列中逆序对的数目。

输入 #1

1
2
6
5 4 2 6 3 1

输出 #1

1
11

说明/提示

对于 \(25\%\) 的数据，\(n \leq 2500\)。

对于 \(50\%\) 的数据，\(n \leq 4 \times 10^4\)。

对于所有数据，\(n \leq 5 \times 10^5\)。

请使用较快的输入输出。

应该不会 \(O(n^2)\) 过 50 万吧 by chen_zhe。

  • 分：取中点，逆序对存在于中点左侧，右侧以及跨中点部分
  • 治：分别统计两侧的逆序对数量，跨中点部分统计如下
  • 合：对左右以及左右merge过程产生逆序对数量求和，统计完后让原数组l到r有序

merge函数伪代码：

1
2
3
4
int f(l,r){
    int m = (l+r)/2;
    return f(l,m)+f(m+1,r)+'''左右merge过程中产生的逆序对数量'''
}

如何统计跨中点部分的逆序对数量：

让i，j分别在两区间右侧开始向左遍历（此时左右区间已经统计完毕并复原）

若arr[i]>arr[j] 则证明该j位置与该j位置之前的位置的数均可以组成逆序对

若arr[i]<=arr[j]，则让j–，继续判断，当j移动到左侧区间时，判定逆序对数为0

以上两种情况发生后让i–，继续统计逆序对

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> PII;
const int N = 5e5 + 10;
const double pi = acos(-1.0);
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
ll arr[N];
ll temp[N];
// 查询跨左右区间的逆序对数
ll merge(int l, int r ,int m){
  ll ans = 0;
  for (int i = m,j=r;i>=l;i--){ // 从左右区间的右侧开始比较
    while(arr[i]<=arr[j]&&j>=m+1) j--; // j不到左区间的情况下以及未发现逆序对时往左遍历
    ans += j-m; // 若发现第一个逆序对(arr[i]>arr[j]&&i<j)，由于已经排序，前面剩下的都可以组成逆序对
  }
  // 归并排序，将查询过的区间进行排序
  int i = l, j = m+1, k = l;
  while(i<=m && j<=r){
    if (arr[i]<=arr[j])temp[k++]=arr[i++];
    else temp[k++]=arr[j++];
  }
  while(i<=m) temp[k++]=arr[i++];
  while(j<=r) temp[k++]=arr[j++];
  for (int i = l;i<=r;i++) arr[i]=temp[i];
  return ans;
}
// 分治，分为左右区间以及跨区间逆序对
ll f(int l, int r){
  if (l==r) return 0;
  ll m = (l+r)/2;
  return f(l,m)+f(m+1,r)+merge(l,r,m);
}
void solve() {
  int n;
  cin >> n;
  for (int i = 1;i<=n;i++) cin >> arr[i];
  cout << f(1,n);  
}
int main()
{
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int tomorin=1;
  //cin >> tomorin;
  while (tomorin--) solve();
  return 0;
}