一、分治
定义
把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
解题步骤
1.分解 2.求解 3.合并
例子
1.归并排序
示例代码
#include <iostream>
using namespace std;
#define MAX 10000
int n,result[MAX];
void merge(int arr[],int arr_tmp[],int l_start,int r_start,int end_num)
{
int arr_len=end_num-l_start+1;
int c_pos=l_start,i=l_start,j=r_start;
while(i<=r_start-1&&j<=end_num)
{
if(arr[i]<arr[j])
arr_tmp[c_pos++]=arr[i++];
else
arr_tmp[c_pos++]=arr[j++];
}
while(i<=r_start-1)
arr_tmp[c_pos++]=arr[i++];
while(j<=end_num)
arr_tmp[c_pos++]=arr[j++];
for(int i=1;i<=arr_len;i++,end_num--)
arr[end_num]=arr_tmp[end_num];
}
void msort(int arr[],int arr_tmp[],int left,int right)
{
int middle=0;
if(left<right)
{
middle=(left+right)/2;
msort(arr,arr_tmp,left,middle);
msort(arr,arr_tmp,middle+1,right);
merge(arr,arr_tmp,left,middle+1,right);
}
for(int i=1;i<=n;i++)
result[i]=arr[i];
}
int main()
{
int num[MAX],tmp[MAX];
cin>>n;
for(int i=1;i<=n;i++)
cin>>num[i];
msort(num,tmp,1,n);
for(int i=1;i<=n;i++)
cout<<result[i]<<" ";
}
例：逆序对个数
Sample input:
6
5 4 2 6 3 1
Sample output:
11
2.其他例题
例1.分数线划定（Luogu P1068)
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define MAX 10000
struct grade
{
int number;
int score;
};
bool cmp(const grade &a,const grade &b)
{
return a.score>b.score;
}
int main()
{
int m,n,line,cnt=0;
grade people[MAX];
cin>>m>>n;
for(int i=1;i<=m;i++)
cin>>people[i].number>>people[i].score;
sort(people+1,people+m+1,cmp);
n=floor(n*1.5);
line=people[n].score;
for(int i=1;i<=m;i++)
{
if(people[i].score<line)
break;
cnt++;
}
cout<<line<<" "<<cnt<<endl;
for(int i=1;i<=cnt;i++)
cout<<people[i].number<<" "<<people[i].score<<endl;
}
