分治

把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

例题：
快速排序：
https://www.acwing.com/problem/content/787/
快速排序的思想就是基于分治。
1.首先设定一个分界值，通过该分界值将数组分成左右两部分。
2.将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。一趟排序过后，左边部分中各个数据元素都小于分界值，而右边部分中各数据元素都大于或等于分界值，且右边部分个数据元素皆大于左边所有数据元素。
3.然后，左边和右边的数据可以看成两组不同的部分，重复上述1和2步骤
当左右两部分都有序时，整个数据就完成了排序。
代码：

void qksort(vector<int>&a,int l,int r)
{
    if(l>=r) return ;
    int i = l-1;
    int j = r+1;
    int x = a[(l+r)>>1];
    while(i<j)
    {
        do i++; while(a[i]<x);
        do j--; while(a[j]>x);
        if(i<j) swap(a[i],a[j]);
    }
    qksort(a,l,j);
    qksort(a,j+1,r);
}

归并排序：将原序列化成一个一个子序列，将已有的子序列进行合并，从而得到完全有序的序列。
代码：

void merge_sort(vector<int>&a,int l,int r)
{
    if(l>=r )return 0;
    int mid =(l+r)>>1;
    merge_sort(a,l,mid);
    merge_sort(a,mid+1,r);
    int k =0;
    int i = l;
    int j = mid+1;
    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 k=0,i=l;i<=r;i++,k++)
    {
        a[i] = tmp[k];
    }
}

为运算表达式设置优先级：
https://leetcode.cn/problems/different-ways-to-add-parentheses/
将表达式看成 x op y的形式，而每个x,y又可以划分成x op y的子问题。
因此可以利用分治的思想，将运算符分为两部分进行递归求解，根据运算符合并两部分的解，得出最终解。

class Solution {
public:
    vector<int> diffWaysToCompute(string expression) {
        int n = expression.size();
        int flag =0;
        vector<int>vec1,vec2,res;
        for(int i=0;i<n;i++)
        {
            if(expression[i]=='+' || expression[i]=='-' || expression[i]=='*')
            {
                flag = 1;
                vec1 =  diffWaysToCompute(expression.substr(0,i));
                vec2 = diffWaysToCompute(expression.substr(i+1,n-i-1));
                for(int&v1:vec1)
                {
                    for(int&v2:vec2)
                    {
                        if(expression[i]=='+') res.push_back(v1+v2);
                        if(expression[i]=='-') res.push_back(v1-v2);
                        if(expression[i]=='*') res.push_back(v1*v2);
                    }
                }
            }
        }
        if(flag ==0) res.push_back(stoi(expression));
        return res;
    }
};

归并应用：

https://www.acwing.com/problem/content/148/
将第一个输入的序列按从小到大进行排序进行，然后依次与后面输入的序列进行组合合并，取最小的前n个，利用堆来进行多路归并。

#include<bits/stdc++.h>
using namespace std;
const int N=2010;
int a[N],b[N],c[N];
int m,n;
void merge()
{
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
    for(int i=0;i<n;i++)
    {
        pq.push({a[0]+b[i],0});
    }
    for(int i=0;i<n;i++)
    {
        auto [s,p] =pq.top();
        pq.pop();
        c[i] =s;
        pq.push({s-a[p]+a[p+1],p+1});//由a[0]+b[i]->a[1]+b[i],进行状态变化。
    }
    for(int i=0;i<n;i++)
    {
        a[i]=c[i];
    }
}
int main(void)
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&m,&n);
        for(int i=0;i<n;i++)scanf("%d",&a[i]);
        sort(a,a+n);
        for(int i=0;i<m-1;i++)
        {
            for(int j=0;j<n;j++)scanf("%d",&b[j]);
            merge();
        }
        for(int i=0;i<n;i++)
        {
            printf("%d ",a[i]);
        }
        printf("\n");
    }
}