分治的一些经典算法与例题（二分）（待完善）_经典分治

分治是什么?

  分治，字面上的解释是“分而治之”，就是把一个复杂的问题分解为两个或更    
多的相同或相似的子·问题，再把子问题分成更小的子问题，直到最后子问
题可以简单的直接求解，原问题的解即子问题的解的合并。——百度
1
2
3

上叙是百度上的正式解释，分治通俗来说，就是一种分割问题的思想。
举个栗子，你的美女同桌zmx要过生日了，为了给她买礼物，你掏出了自己的零花钱，你决定先确定一下你的经济实力。于是你将RMB按金额分类放好，这样你只需要输出每叠钱的数目就能轻松的算出总金额。
分治策略中，我们通常用到三个步骤：（1）分解（2）解决（3）合并

在上述栗子里，为了数出总金额，我们想到总金额不就是各种面额的纸币的金额总数相加吗（分解），于是原问题便被我们分解为了求不同面额纸币总数，这是我们能轻松解决的问题（解决），在数出每叠钱的总价值后我们只需要将所有价值加在一起，变求得原问题（合并）

分治的一个工具，一个方法——二分

二分是在分治问题里常常遇到的一种简化问题，求取极值，特值的一种方式
无论是惠施的一尺之棰还是芝诺的悖论都运用了二分法的思想，接下来我将通过几个经典的算法和例题来展示分治和二分的奇妙。

经典算法

二分查找

相信大家都玩过一个猜数的游戏，游戏内容是一个玩家在心里想一个数，另一个玩家要在有限的次数里猜出这个数，想数的玩家会根据猜数的玩家说出的数提示是小了还是大了。假如游戏的范围在1~100内，总有愣头青想着就单单100个数，我从1开始一个推就行了。这种方法虽然可行，但不高效，当数据较大时就显得鸡肋。

于是二分查找法应运而生，其算法基本思想便是从数据范围的中值开始问起，这样便能一次排除一半的数据，下一次再从符合条件范围的中值问，一次次的缩减范围直到找到为止。
时间复杂度：考虑最坏情况下直到查到最后一个数才查出，假如一共有n个数，就需要查找log₂n次 于是算法时间复杂度为O（logn）
代码：

int n;//想到的数
scanf("%d",&n);
int i=1,j=100;
int mid=(i+j)>>1//找出中值
while(i<=j){
  if(mid==n){//如果找到
    printf("ok");
    return 0;
  }
  if(mid>n) j=mid-1;//如果中值大于n 就将上限变小
  else i=mid+1;//反之亦然
}
printf("no");
return 0;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

这种将数据分堆处理的思想启发了很多算法，例如快速排序，归并排序等。

快速排序

每次选出一个基准值，使基准值左边的所有数据小于该值，基准值右边的值大于该值，然后再在右边和左边区间在使用这个方法归类，当区间无法再分时，数列就排好了。

选数的标准并不影响最后的结果，每次选的标准值值时都使其左值小于它，右值大于它，所以它的位置排对了，只要我们将所有数的位置排对，那么整个数列就排好序了。

为了实现整个算法，让我们回顾我们都做了什么，（）我们先是选出了一个标准值，然后将小于他的所有数都放在一边，另一边全是大于它的数，于是我们需要从两边分别遍历一边整个数列，可以定义两个指针分别指向该数列的两端，假如从右边先开始，因为该标准值的右边所有数都要大于它，所以要找到第一个小于它的数，当找到时，就将左边的指针右移，直到找到第一个大于它的值然后便将两值调换，在使右指针左右，重复上面步骤，直到两个指针相遇，就将标准值与该位置的值调换。

但除了调换数据还有一种类似于从盒子里取数的方法，它并没有交换值而是创建了一个空盒子，在数据较多时可能更优
具体见图

具体代码实现如下：

#include <stdio.h>
int a[100005];
void quicksort(int n,int m){
	int i=n,j=m; 
	int len=m-n;
	if(i>=j) return;//结束递归条件 
	int k=a[n];//类似于拿另一个盒子装a[n],原位置相当于被拿空 
	while(i<j){
		while(i<j&&a[j]>=k){
			j--;//直到出现a[j]<k,注意条件为<=否则可能会陷入死循环 
		}
		a[i]=a[j];//将a[j]放入空盒子，a[j]为空盒子 
		while(i<j&&a[i]<=k){
			i++;
		}
		a[j]=a[i];
	}
	a[i]=k;//将基准数放入空盒子中 
	quicksort(n,i-1);
	quicksort(i+1,m);//注意是i+1，因为i已经排好序了，在从i开始会陷入死循环 
}
int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	quicksort(0,n-1);
    for(int i=0;i<n;i++){
        if(i!=n-1)	printf("%d ",a[i]);
        else printf("%d\n",a[i]);
	}
	return 0;
}
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

归并排序

如果我们只有2个数，我们可以轻而易举的排好序，如果我们能将一个数列分为很多个小组，分别进行排序，最后再进行合并，是不是就能排好整个序列的顺序了呢？

想一想我们要做些什么？
（1）我们需要将整个数列分为一个个小组，什么能帮我们做到？还记得快速排序吗，二分和递归可以帮助我们完成分组这个工作
（2）合并，我们需要将排好序的两个不同小组进行合并，先让我们来看看合并时我们的小组内具有什么特性，有序，每次合并时我们各小组内的数据是有序的，当各小组只有1个数时它当然是有序的，在我们合并时可以轻松排好序，下一次我们合并时一个小组内有两个数，这俩个数也是有序的。这可以说明每次合并时各小组内的数是有序的，而在我们进行合并后，这一区间内的数也变为有序。
对于两个有序序列的组合合并见图：




于是在函数里我们需要两个步骤（1）分组（2）合并
代码见下：

#include <stdio.h>
int a[100005];
void merge(int low,int mid,int high){
	int b[100005]={0};//存储排序好的数列 
	int k=0;
	int *p=&a[low],*q=&a[mid+1];//两个哨兵，分别指向两组数据队首 
	while(p<=&a[mid]&&q<=&a[high]){//两组数据一旦有一组数据选完就结束 
		if(*p<*q){
			b[k++]=*p++;
		}else{
			b[k++]=*q++;
		}
	}
	while(p<=&a[mid]) b[k++]=*p++;//将没选完的那组数据剩余元素全部选出 
	while(q<=&a[high]) b[k++]=*q++;
	for(int i=low,k=0;i<=high;i++){
		a[i]=b[k++];//将排好序的数列复制回去 
	}
}
void mergesort(int low,int high){
	if(low<high){
		int mid=(low+high)>>1;
		mergesort(low,mid);
		mergesort(mid+1,high);//加一防止死循环 
		merge(low,mid,high);//合并 
	}
}
void print(int n){
	for(int i=0;i<n;i++){
	if(i!=n-1)	printf("%d ",a[i]);
	else printf("%d\n",a[i]);
	} 
}
int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	mergesort(0,n-1);
	print(n);
	return 0;
}
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

例题

第k小整数

输入n个数，输出该列数中第k小的数（1≤n<5000000 且 n 为奇数）（第0小的数是最小的数，以此类推）
第一次看到这道题时，相信大部分人想到的是先排序在遍历，如果使用O(nlogn)的排序，在进行排序后遍历复杂度为O(k),总时间复杂度为O(k+nlogn),可能会超时

还记得快速排序吗？每次我们选出的基准值都是将其放在了其正确的位置，所以我们只需要比较该位置i与k的大小，如果i<k,则在右边寻找，反之则在左边寻找，直到标准值位置i=k时寻找成功，时间复杂度为O（n*logn）
代码实现：

#include <stdio.h>
int k;
int a[5000005];
void quicksort(int low,int high){
	int t=a[low];
	int i=low,j=high;
	while(i<j){
		while(i<j&&a[j]>=t){
			j--;
		}
		a[i]=a[j];
		while(i<j&&a[i]<=t){
			i++;
		}
		a[j]=a[i];
	}
	if(i==k) printf("%d",t);//如果该位置为k 则寻找正确
	else if(i>k) quicksort(low,i-1);//如果该位置 大于k 则应该在更小的区间去寻找
	else quicksort(i+1,high);//如果该位置小于k 则应该在更大的区间去寻找
}
int main(){
	int n;
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	quicksort(0,n-1);
	return 0;
}
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

分割数列

将m个数分割为n段使每段数字和的最大值最小（不可调换数字顺序）（1<n,m<1e5）
例如 ：1 2 3 4 5 分为3段 可分为 1,2 3,4 5；数字和最大值为 9
刚看到这道题时，我第一反应是前缀和加搜索，算出所有数前缀和然后从前缀和数列里选出n个数字就能算出一次分割的最大值，经过搜索就可以列出所有情况，但时间复杂度为O(mⁿ)太高会超时。
在求极限值或特值时可以考虑到二分，我们可以将数字和的最大值当做二分值n，然后遍历数列看n是否可以成立，如果可以成立，则在low，n之间再取一个数，再看能否成立；如果不能成立，则在n，high，之间再取一个数，看能否成立。时间复杂度约为O(m*logmax)
代码见下：

#include <stdio.h>
int n,m;
int a[100005];
int pre;
int ans;
int find(int x){
	int t=m-1;
	for(int i=0;i<n;i++){
		if(t==0){
			if(a[n-1]-a[pre]<=x){
				ans=x;
				return 1;
			}
			else {
			return 0;	
			}
		}
		if(pre==0){
			if(a[i]>x){
				pre=i-1;
				t--;
			}
		}else{
			if(a[i]-a[pre]>x){
				pre=i-1;
				t--;
			}
		}
	}
	ans=x;
	return 1;
}
int main(){
	scanf("%d%d",&n,&m);
	scanf("%d",&a[0]);
	for(int i=1;i<n;i++){
		scanf("%d",&a[i]);
		a[i]+=a[i-1];
	}
	int low=0,high=100000;
	while(low<=high){
		pre=0;
		int i=(low+high)>>1;
		int x=find(i);
		if(x==0){
			low=i+1;
		}else{
			high=i-1;
		}
	}
	printf("%d",ans);
	return 0;
}
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

类似于跳石头——洛谷