一、概述

1、基本思想及策略

分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

如果原问题可分割成k个子问题，1<k≤n，且这些子问题都可解并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

2、分治法适用的情况

分治法所能解决的问题一般具有以下几个特征：

1. 该问题的规模缩小到一定的程度就可以容易地解决

2. 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

3. 利用该问题分解出的子问题的解可以合并为该问题的解；

4. 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；

第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；

第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。

第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

1、二分搜索

（1）当前问题能不能切分？

答：能切分，因为数组按照升序来排列。所以当x大于某个元素array[mid]时，x一定在array[mid]的右边。以此再来切分。每次切一半

（2）分解出来的子问题相同吗？

答：相同，每个子问题的数据集都是父问题的1/2倍。并且每次只比较子问题的中间的数据

（3）子问题的解能合并为父问题的解吗？

答：不需要合并，子问题的解即为父问题的解。

（4）子问题之间相互独立吗？

答：独立，子问题只是判断，不需要和父问题有很强的关联性（这里可以参考一下动态规划算法，就能理解子问题之间怎么判断是独立的）

2、合并排序

（1）当前问题能切分吗？

答：能，最简单的就是两个数之间的比较，这个数组可以看成多个两个数来比较

（2）分解出来的子问题是否相同？

答：相同，都是两个数比较大小。

（3）子问题的解能够合成父问题的解吗？

答：每两个有序数组再按照一定顺序合起来就是最终的题解。这里就是有个合并的过程

（4）子问题之间相互独立吗？

答：独立，分到最小的时候子问题之间互不影响。

二、分治法经典例题

1、棋盘覆盖问题？？

原理https://blog.csdn.net/qq_30268545/article/details/80600064

实现https://www.cnblogs.com/yinbiao/p/8666209.html

#include<stdio.h>
#define max 1024
int cb[max][max];//最大棋盘
int id=0;//覆盖标志位
int chessboard(int tr,int tc,int dr,int dc,int size)//tr，tc代表棋盘左上角的位置，dr ,dc代表棋盘不可覆盖点的位置,size是棋盘大小
{if(size==1)//如果递归到某个时候，棋盘大小为1，则结束递归{return 0;}int s=size/2;//使得新得到的棋盘为原来棋盘大小的四分之一int t=id++;if(dr<tr+s&&dc<tc+s)//如果不可覆盖点在左上角，就对这个棋盘左上角重新进行棋盘覆盖{chessboard(tr,tc,dr,dc,s);}else//因为不可覆盖点不在左上角，所以我们要在左上角构造一个不可覆盖点{cb[tr+s-1][tc+s-1]=t;//构造完毕chessboard(tr,tc,tr+s-1,tc+s-1,s);//在我们构造完不可覆盖点之后，棋盘的左上角的四分之一又有了不可覆盖点，所以就对左上角棋盘的四分之一进行棋盘覆盖}if(dr<tr+s&&dc>=tc+s)//如果不可覆盖点在右上角，就对这个棋盘右上角的四分之一重新进行棋盘覆盖{chessboard(tr,tc+s,dr,dc,s);}else//因为不可覆盖点不在右上角，所以我们要在右上角构造一个不可覆盖点{cb[tr+s-1][tc+s]=t;chessboard(tr,tc+s,tr+s-1,tc+s,s);//在我们构造完不可覆盖点之后，棋盘的右上角的四分之一又有了不可覆盖点，所以就对右上角棋盘的四分之一进行棋盘覆盖}if(dr>=tr+s&&dc<tc+s)//如果不可覆盖点在左下角，就对这个棋盘左下角的四分之一重新进行棋盘覆盖{chessboard(tr+s,tc,dr,dc,s);}else//因为不可覆盖点不在左下角，所以我们要在左下角构造一个不可覆盖点{cb[tr+s][tc+s-1]=t;chessboard(tr+s,tc,tr+s,tc+s-1,s);//在我们构造完不可覆盖点之后，棋盘的左下角的四分之一又有了不可覆盖点，所以就对左下角棋盘的四分之一进行棋盘覆盖}if(dr>=tr+s&&dc>=tc+s)//如果不可覆盖点在右下角，就对这个棋盘右下角的四分之一重新进行棋盘覆盖{chessboard(tr+s,tc+s,dr,dc,s);}else//因为不可覆盖点不在右下角，所以我们要在右下角构造一个不可覆盖点{cb[tr+s][tc+s]=t;chessboard(tr+s,tc+s,tr+s,tc+s,s);//在我们构造完不可覆盖点之后，棋盘的右下角的四分之一又有了不可覆盖点，所以就对右下角棋盘的四分之一进行棋盘覆盖}//后面的四个步骤都跟第一个类似
}
int main()
{printf("请输入正方形棋盘的大小（行数）:\n");int n;scanf("%d",&n);printf("请输入在%d*%d棋盘上不可覆盖点的位置:\n",n,n);int i,j,k,l;scanf("%d %d",&i,&j);printf("不可覆盖点位置输入完毕，不可覆盖点的值为-1\n");cb[i][j]=-1;chessboard(0,0,i,j,n);for(k=0;k<n;k++){//第一列没有缩进printf("%2d",cb[k][0]);//后面的列有缩进for(l=1;l<n;l++){printf(" %2d",cb[k][l]);}printf("\n");}return 0;
}

2、循环赛日程表？？？

https://blog.csdn.net/zhangguohao666/article/details/84205657

3、线性时间选择

https://www.jianshu.com/p/bf47d7b4a43d

4、最接近点对问题（了解）

https://blog.csdn.net/qq_22238021/article/details/78852337

三、二分法

1、概念

二分法查找是一种非常高效的搜索方法，主要原理是每次搜索可以抛弃一半的值来缩小范围。其时间复杂度是O(log2n)，一般用于对普通搜索方法的优化。

2、解题思路

（1）确定二分类型

（2）检查数据是否从小到大，否则调整（注意是否不影响正确结果）

（2）确定变量，确定范围left right（范围大点没关系）

（3）确定验证条件及方法（难点）

统一格式如下：先考虑小大，再根据题意考虑等号

while有=号，r = m - 1，无 r = m

应用

int main()
{int i,low,high,mid;while(low<=high)			//？？根据变量范围而定{mid=(low+high)/2;if (judge(mid)) low=mid+1;//？？最大化  最小化 r = mid - 1else high=mid-1;//？？}cout<<low-1<<endl;//if (judge(mid)) low=mid+1;即可！return 0;
}

整数

int left_bound(int[] nums, int target) {int left = 0;int right = nums.length; 		//数组元素个数（题目所给总个数）		while (left < right) {  int mid = (left + right) / 2;//=位置根据题意自定！！if (nums[mid] < target) {left = mid + 1; } else if (nums[mid] > target) {right = mid;    }}return ...		
}

小数：要大返回r，要小返回l

int left_bound(int[] nums, int target) {int left = 0;int right = nums.length; 		    //数组元素个数（题目所给总个数）		while ((right - left) > ...) {  	//对n位小数精度要求，>1e-(n+1)int mid = (left + right) / 2;//=位置根据题意自定！！（如果没有最大最小化要求，则=随意）if (nums[mid] < target) {left = mid; } else if (nums[mid] > target) {right = mid;    }}return ...		
}

3、适用条件

（1）该数组已经排序

（2）该数组数据量巨大，需要对处理的时间复杂度进行优化

（3）一般要求找到的是某一个值或一个位置。

4、二分法的分类及注意事项

详细原理、定义、思路见下：

https://www.cnblogs.com/kyoner/p/11080078.html

5、基本的二分搜索

int binarySearch(int[] nums, int target) {int left = 0; int right = nums.length; while(left < right) {    //1、由初始化值知搜索区间为 [left, right)int mid = (right + left) / 2;if(nums[mid] == target)return mid; 	 //2、找到返回即可else if (nums[mid] < target)left = mid + 1;  //由1决定往右接着搜索[mid + 1, right)else if (nums[mid] > target)right = mid;     //由1决定往左接着搜索[left, mid)}return -1;				 //3、找不到返回-1
}

（1）二分查找

import java.util.*;
public class Main {public static void main(String[] args) {	Scanner in = new Scanner(System.in);int[] a = new int[]{1,6,9,14,15,17,18,23,24,28,34,39,48,56,67,72,89,92,98,100};int x = in.nextInt();int l = 0,r = a.length;while(l < r) {int mid = (l + r) / 2;if(a[mid] == x) {System.out.println(mid);break;}else if(a[mid] < x) {l = mid + 1;}else {r = mid;}}}}

（2）求平方根

https://www.cnblogs.com/cs-whut/p/11212022.html

import java.util.*;
public class Main {public static void main(String[] args) {	Scanner in = new Scanner(System.in);float x = in.nextFloat();float l = 1, r = x;while((r - l) > 1e-5) {float mid = (l + r) / 2;if(mid * mid > x) {r = mid;}else {l = mid;}}System.out.printf("%.4f",l);}}

6、找左侧边界（最小化最大值问题）

对象：要求的最小化的值（一般就是要求的值）

最小化：寻找左侧边界

最大值：拿来应用的（因为说的是本例）

int left_bound(int[] nums, int target) {int left = 0;int right = nums.length; while (left < right) {  //1、由初始化值知搜索区间为 [left, right)int mid = (left + right) / 2;if (nums[mid] == target) {right = mid;    //2、收紧右侧边界以锁定左侧边界，right = mid（右开）} else if (nums[mid] < target) {left = mid + 1; //同（由1决定）} else if (nums[mid] > target) {right = mid;    //同（由1决定）}}return right;			//3、由2决定mid = right（最终left == right，故left也可）
}

合并=位置

int left_bound(int[] nums, int target) {int left = 0;int right = nums.length; while (left < right) {  //1、由初始化值知搜索区间为 [left, right)int mid = (left + right) / 2;if (nums[mid] < target) {left = mid + 1; //同（由1决定）} else if (nums[mid] >= target) {right = mid;    //同（由1决定）}}return right;			//3、由2决定mid = right（最终left == right，故left也可）
}

（1）数列分段？

怎么计算出当前每段和的最大值情况下所能分割的段数？？？

https://www.cnblogs.com/cs-whut/p/11216941.html

import java.util.*;
public class Main {public static void main(String[] args) {	Scanner in = new Scanner(System.in);int n = in.nextInt();int m = in.nextInt();int[] a = new int[n];int l = 0,r = 0; for(int i = 0;i < n;i++) {a[i] = in.nextInt();r += a[i];l = Math.max(l, a[i]);}while(l < r) {int mid = (r + l) / 2;if(judge(a,mid,m)) {r = mid;}else {l = mid + 1;}}System.out.println(r);}//计算出当前每段和的最大值情况下所能分割的段数？？？public static boolean judge(int[] a,int mid,int m) {int num = 0;int sum = 0;for(int i = 0;i < a.length;i++) {sum += a[i];if(sum > mid) {		//？？sum = a[i];		//？？num ++;}}if(num + 1 <= m) {		//？？return true;}return false;			}}

7、找右侧边界

（一）最大化最小值问题

最大化：寻找右侧边界

最小值：拿来应用的（因为说的是本例）

int right_bound(int[] nums, int target) {int left = 0;int right = nums.length;while (left < right) {  //1、由初始化值知搜索区间为 [left, right)int mid = (left + right) / 2;if (nums[mid] == target) {left = mid + 1; //2、收紧左侧边界以锁定右侧边界，left = mid + 1(左闭)} else if (nums[mid] < target) {left = mid + 1; //同（由1决定）} else if (nums[mid] > target) {right = mid;    //同（由1决定）}}return left - 1; 		//3、由2决定mid = left - 1（最终left == right，故right - 1也可）

合并=位置

int right_bound(int[] nums, int target) {int left = 0;int right = nums.length;while (left < right) {  //1、由初始化值知搜索区间为 [left, right)int mid = (left + right) / 2;if (nums[mid] <= target) {left = mid + 1; //同（由1决定）} else if (nums[mid] > target) {right = mid;    //同（由1决定）}}return left - 1; 		//3、由2决定mid = left - 1（最终left == right，故right - 1也可）

（1）跳石头

验证条件：应搬走石头数是否符合题意

https://www.cnblogs.com/cs-whut/p/11216980.html

#include <iostream> 
#include <algorithm>using namespace std;
int d[50005],l,n,m;
bool judge(int mid)
{int start=0,x=0,i; // start表示每次落脚点的坐标，每落一次地更新一次startfor(i=1;i<=n;i++)	//一直到n（n+1是终点不能去掉）{if (d[i]-start<mid)x++;   // x表示去掉的石头数，如果mid大于要跳的距离，就去掉当前这个石头elsestart=d[i];  // 此时落在石头上}if (l-start<mid)   // 判断最后一跳跳的距离要是小于mid的话那是不可以的！！return false;if(x>m)          //  要是x>m就说明最小距离mid太大啦return false;return true;
}int main()
{int left,right,mid,ans,min = 0x7fff,i;cin>>l>>n>>m;for(i=1;i<=n;i++)cin>>d[i];d[0] = 0;d[n + 1] = l;//sort(d,d+(n+1));for(i = 0; i <= n; i++)if (d[i+1]-d[i]<min)min = d[i+1]-d[i];left = min, right = l;while(left<=right){mid=(left+right)/2;if (judge(mid)){left=mid+1;}elseright=mid-1;}cout<<left-1<<endl;return 0;
}

（2）好斗的牛

验证条件：能否放下C头牛

https://www.cnblogs.com/cs-whut/p/11216980.html

#include <iostream>
#include <algorithm>using namespace std;
const int N = 100005;
int p[N], n, c;
bool judge(int x)
{int cnt = 1, tmp = p[0];		//第一个就放牛了？for(int i = 1; i < n; i++){if(p[i] - tmp >= x){cnt++;tmp = p[i];if(cnt >= c)    		//可以放下C头牛return true;}}return false;
}int main()
{int i,low,high,mid;cin>>n>>c;for(i=0;i<n;i++)scanf("%d",&p[i]);sort(p,p+n);high=(p[n-1]-p[0])/(c-1);low=0;while(low<=high){mid=(low+high)/2;if (judge(mid)) low=mid+1;else high=mid-1;}cout<<low-1<<endl;return 0;
}

（二）最大化平均值问题

小数？

    while ((right-left)>1e-4)		//因1，故left和right会无限逼近{mid=(left+right)/2;if(judge(mid)>=k) left=mid;  //1.小数不能加一减一else right=mid;}

（1）木材加工

整数

验证条件：能否切出k段

https://www.cnblogs.com/cs-whut/p/11212022.html

import java.io.*;
import java.util.*;
public class Main {public static void main(String[] args) throws IOException {	StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));in.nextToken();int n = (int)in.nval;in.nextToken();int k = (int)in.nval;int[] s = new int[n];//最短是1int l = 1,r = 0;for(int i = 0;i < n;i++) {in.nextToken();s[i] = (int)in.nval;r = Math.max(r, s[i]);}while(l <= r) {int mid = (l + r) / 2;if(judge(mid,k,s)) {l = mid + 1;}else {r = mid - 1;}}   //查找范围是[1,r]，为什么能做到如果连1cm长的小段都切不出来，输出”0”？查找的是左边界out.print(l - 1);out.close();}public static boolean judge(int mid,int k,int[] s) {int sum = 0;for(int i = 0;i < s.length;i++) {sum += s[i] / mid;if(sum >= k) {return true;}}return false;}
}

（2）切绳子

小数，思路类似于（1）

https://www.cnblogs.com/cs-whut/p/11217130.html

（3）Pie （POJ 3122）

小数

23333，说了一堆，结果和切绳子问题一样的

https://www.cnblogs.com/cs-whut/p/11217130.html

8、使用Map

用于记录个数

（1）A-B 数对

import java.util.*;
import java.io.*;
public class Main {static Map<Integer,Integer> map = new HashMap<Integer,Integer>();public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] nums = br.readLine().trim().split(" ");int n = Integer.parseInt(nums[0]);int c = Integer.parseInt(nums[1]);int[] s = new int[n];nums = br.readLine().trim().split(" ");for(int i = 0;i < n;i++) {s[i] = Integer.parseInt(nums[i]);Integer num = map.get(s[i]);		//用Integer接收nullif(num == null) {map.put(s[i], 1);}else {map.put(s[i], num + 1);}}long sum = 0;for(int i = 0;i < n;i++) {if(map.containsKey(s[i] + c)) {		//判断Key是否存在sum += map.get(s[i] + c);}}System.out.println(sum);}}

9、动态规划+二分？？

（1）递增

https://www.luogu.com.cn/problem/P3902

（2）导弹拦截

四、三分法

关键在于依题意构造出f//求f最小值while(left+eps<=right){mid=(left+right)/2;midmid=(mid+right)/2;if(f(mid)<f(midmid))	//=在这里也可right=midmid;elseleft=mid;}
//求f最大值while(left+eps<=right){mid=(left+right)/2;midmid=(mid+right)/2;if(f(mid)<f(midmid))left=mid;elseright=midmid;}//left right midmid mid都近似，均可使用
printf("%.4f\n",f(left));

1、三分 HDU - 3714

https://www.cnblogs.com/xuejianye/p/5533182.html

2、三分套三分 BZOJ1857

https://www.cnblogs.com/aininot260/p/9499390.html

http://www.cfzhao.com/index.php/2018/02/11/bzoj1857-hdu3400-传送带问题（三分套三分）/

第一层三分：假设F点固定，取最优E点

第二层三分：F点移动时，对两个固定的F点，会有各自的最优时间，取最优F点

#include<cstdio>
#include<cmath> 
#define eps 1e-3
int ax,ay,bx,by;
int cx,cy,dx,dy;
int p,q,r;
inline int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}return x*f;
}
double dis(double x1,double y1,double x2,double y2)
{return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}//第一层三分
double cal(double x,double y)  //x和y是计算完的AB上的点 
{double lx=cx,ly=cy,rx=dx,ry=dy;double x1,y1,x2,y2,t1,t2;while(fabs(rx-lx)>eps||fabs(ry-ly)>eps){x1=lx+(rx-lx)/3;y1=ly+(ry-ly)/3;x2=lx+(rx-lx)/3*2;y2=ly+(ry-ly)/3*2;t1=dis(ax,ay,x,y)/p+dis(x,y,x1,y1)/r+dis(x1,y1,dx,dy)/q;t2=dis(ax,ay,x,y)/p+dis(x,y,x2,y2)/r+dis(x2,y2,dx,dy)/q;if(t1>t2){lx=x1;ly=y1;}else {rx=x2;ry=y2;}}//计算完lx和ly是CD上的点 return  dis(ax,ay,x,y)/p+dis(x,y,lx,ly)/r+dis(lx,ly,dx,dy)/q;
}
int main()
{ax=read(),ay=read(),bx=read(),by=read();cx=read(),cy=read(),dx=read(),dy=read();p=read(),q=read(),r=read();double lx=ax,ly=ay,rx=bx,ry=by;double x1,y1,x2,y2,t1,t2;//第二层三分while(fabs(rx-lx)>eps||fabs(ry-ly)>eps){x1=lx+(rx-lx)/3;y1=ly+(ry-ly)/3;x2=lx+(rx-lx)/3*2;y2=ly+(ry-ly)/3*2;t1=cal(x1,y1);t2=cal(x2,y2);  //用CD结果迭代算AB if(t1>t2) {lx=x1;ly=y1;}else {rx=x2;ry=y2;}}printf("%.2lf\n",cal(lx,ly));//传AB终值算答案 return 0;
}