【算法】分治算法

分治算法通过递归分解大问题为若干个子问题, 解决每个子问题后合并各个子问题, 直到合并为原来的大问题.

归并排序

归并排序是经典的分治解决问题的算法, 通过分解数组, 递归求解, 合并排序这三个步骤对数组排序.

先分析归并排序的复杂度, 由于每次合并需要遍历所有数组, 共 $n$ 次, 然后需要遍历每一层, 一共有 $log_2n$ 层, 所以归并排序的复杂度为 $O(nlogn)$ , 是稳定的排序算法.

由于归并过程允许我们对每一个子问题操作, 所以归并排序可以解决很多问题, 以一道题目为例:

这道题在合并过程中, 可以通过合并右边那部分数组的移位差来获得逆序对的个数, 比如 5 和 4 合并时, 4 从第 1 位移到了第 0 位, 所以逆序对个数+1, 同理 45 和 26 合并时, 2 从第 2 位移到了第 0 位, 逆序对+2… 这里由于只有右半部分会产生逆序对, 需要定义一个 mid 变量去获取归并时的中间值,确保只对左半部分求移位差, 如下图:

代码为:

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<iostream>
using namespace std;
int num[500010];
int tmp[500010];
int res;

void merge(int start, int mid, int end){
    int i = start;
    int j = mid+1;
    int idx = 0;
    while(i<=mid&&j<=end){
        if(num[i]>num[j]){
            tmp[idx++] = num[j++];
            res += mid-i+1;
        }
        else{
            tmp[idx++]=num[i++];
        }
    }
    while(i<=mid){
        tmp[idx++]=num[i++];
    }
    while(j<=end){
        tmp[idx++]=num[j++];
    }
}

void merge_sort(int start, int end){
    while(start>=end){
        return
    }
    int mid = (start+end)/2
    merge_sort(start, mid);
    merge_sort(mid+1,end);
    merge(start,mid,end);
    for(int i=start;i<=end;i++){
        num[i]=tmp[i-start];
    }
}

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>num[i];
    }
    res = 0;
    merge_sort(0,n-1);
    cout<<res<<endl;
    return 0;
}

分治法求解最大和子序列

例题:

这道题与上一章暴力求解法的是一道题, 这次采用分治法去求解, 在这里, 大问题是求整个数组的最大子序列和, 我们将这个问题分成多个区间去求解, 即就是求每个区间的最大子序列和, 然后再在合并的时候去判断怎么获得最大子序列和.

合并的时候要算 3 种情况:

  • $S1$ 为左半部分的最大子序列和
  • $S2$ 为右半部分的最大子序列和
  • $S3$ 为合并后包括 mid 和 mid+1 这两个元素的最大子序列和, 这里要针对 mid 往左找最大子序列和, 针对 mid+1往右找最大子序列和, 因为已经分别固定了开头, 所以这个查找就很简单, 直接线性遍历并记录最大值就好就好.

最后求解 $max{S1,S2,S3}$, 就是合并后的最优解了.

代码为:

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include<cstring>
using namespace std;
int a[100001];
struct node{
    int left,right,sum;
    node(int l,int r,int s):
    left(l),right(r),sum(s){}
};

node merge_func(int low,int mid,int high){
    node merge(0,0,0);
    int sum=0;
    int max_left = -10000;
    for(int i=mid;i>=low;i--){
        sum+=a[i];
        if(sum>max_left){
            max_left = sum;
            merge.left = i;
        }
    }
    sum = 0;
    int max_right = -10000;
    for(int i=mid+1;i<=high;i++){
        sum+=a[i];
        if(sum>max_right){
            max_right = sum;
            merge.right = i;
        }
    }
    //cout<<max_left<<" "<<max_right<<endl;
    merge.sum = max_left + max_right;
    return merge;
}


node merge1(int low,int high){
    if(low==high)
        return node(low,high,a[low]);
    int mid = (low+high)/2;
    node n1 = merge1(low,mid);
    node n2 = merge1(mid+1,high);
    node n3 = merge_func(low, mid, high);
    if(n1.sum>=n2.sum && n1.sum>=n3.sum){
        return n1;
    }
    if(n2.sum>=n1.sum && n2.sum>=n3.sum){
        return n2;
    }
    else{
        return n3;
    }
}

int main(){
    int n;
    cin>>n;
    int case_num = 0;
    while(n--){
        memset(a, 0, sizeof(a));
        int m;
        cin>>m;
        for(int i=0;i<m;i++){
            cin>>a[i];
        }
        node ans = merge1(0, m-1);
        if(case_num)
            cout<<endl;
        cout<<"Case "<<++case_num<<":"<<endl;
        cout<<ans.sum<<" "<<ans.left+1<<" "<<ans.right+1<<endl;
    }
}

分治法求解棋盘问题

题目:

这道题别被他的三角形骗了, 实际上使用分治做的, 将棋盘分割成四部分, 因为肯定有一个部分存在特殊方格, 另外三个部分在中心部分填如三角形即可, 示意图如下:

对于有特殊方块的区域, 就继续按照特殊方块分治, 对于没有特殊方块的区域, 就把用三角形填入的那个一个方格当成特殊方块, 继续分治.

代码为:

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
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
using namespace std;

int num=0;
int board[1000][1000];
// c, r 是起始点的横纵坐标, x,y 是特殊方格的横纵坐标, s 是当前棋盘的 size
void chessboard(int c, int r, int x, int y, int s){
    if(size==1){
        return;
    }
    int cnt = ++num;
    int s = size/2; //分割棋盘
    int midx = c+s-1;
    int midy = r+s-1;
    // 左下
    if(x<=midx && y<=midy){
        // 如果存在特殊方格就继续分治
        chessboard(c,r,x,y,s);
    }
    else{
        // 否则将三角形覆盖的那个方格当做特殊方格继续分治
        board[midx][midy] = cnt;
        chessboard(c,r,midx,midy,s);
    }
    // 右下
    if(x>midx && y<=midy){
        chessboard(c+s,r,x,y,s);
    }
    else{
        board[midx+1][midy] = cnt;
        chessboard(c+s,r,midx+1,midy,s);
    }
    //左上
    if(x<=midx && y>midy){
        chessboard(c,r+s,x,y,s);
    }
    else{
        board[midx][midy+1] = cnt;
        chessboard(c,r+s,midx,midy+1,s);
    }
     //右上
    if(x>midx && y>midy){
        chessboard(c+s,r+s,x,y,s);
    }
    else{
        board[midx+1][midy+1] = cnt;
        chessboard(c+s,r+s,midx+1,midy+1,s);
    }
}

int main(){
    int k,x,y;
    cin>>k>>x>>y;
    board[x][y] = 0;
    // 用 1<<k 获取棋盘分治的个数 2 的 k 次方
    chessBoard(1, 1, x, y, (1<<k));
    for(int i=1;i<=(1<<k);i++){
        for(int j=1;j<=(1<<k);j++){
            cout<<board[i][j]<<" ";
        }
        cout<<endl;
    }
}