分治

1.解释

把一个问题分解成多个不同子问题，当子问题可以迎刃而解时，整个问题也就迎刃而解

优点：可以将复杂的问题简单化，让问题更好解决

缺点：很容易扣细节就绕进去了，很难使人相信这东西的正确性

2.步骤

分而治之


1.尝试去分解问题（最难的一步）

2.不断分解直到没法继续分解

3.利用简单的求复杂的


因为这一段实在是 难理解。所以我配两个例子

1.斐波那契数列

天坑

我学会证明就来填

2.线段树

其实这个很简单。就是把一段分解成左和右，在继续分解左右的左右

3.例题

将读入的 \(N\) 个数从小到大排序后输出。

思路：不断分解几个数，分割为左部分和右部分（对应分解），然后没法分解时再比较相邻左子树右子树上的两个数大小，合并，就轻而易举的解决了（归并排序）

代码:

// 注：四个数组的下标均从 0 开始。
// 请在主函数内设置随机种子，例如 srand(time(0))，否则可能会超时。
int randint(int l, int r){ // 生成在 [l, r] 之间的随机数
	return rand() % (r - l + 1) + l;
}
void qsort(int l, int r){ // l 为左端点，r 为右端点
	if(l >= r){ // 如果长度为 0 或 1 就返回
		return;
	}
	int num = randint(l, r), ind1 = 0, ind2 = 0, ind3 = 0; // 随机选择一个数，并定义三个作为下标的变量来记录长度、存放数据
	for(int i = l;i <= r;i++){ // 将 a 中的数分别分到 b, c, d（如上所述）
		if(a[i] < a[num]){
			b[ind1++] = a[i];
		}
		else if(a[i] == a[num]){
			c[ind2++] = a[i];
		}
		else{
			d[ind3++] = a[i];
		}
	}
	for(int i = 0;i < ind1;i++){ // 将 b, c, d 中的数重新放回 a
		a[i + l] = b[i];
	}
	for(int i = 0;i < ind2;i++){
		a[i + ind1 + l] = c[i];
	}
	for(int i = 0;i < ind3;i++){
		a[i + ind1 + ind2 + l] = d[i];
	}
	qsort(l, l + ind1 - 1); // 继续递归，排序原来的 b 和 d
	qsort(l + ind1 + ind2, r);
}

by lg大神@Allen_123

4.技巧

明白一个函数的作用并相信它能完成这个任务，千万不要跳进这个函数里面企图探究更多细节， 否则就会陷入无穷的细节无法自拔。

这里有个亲身经历



作者在考今年\(CSP\)时\(T2\)打了个\(DFS\)，在写\(DF\)S时我就一直在想他递归到最后是什么样子的，耽误了\(1h\)！！！

永远相信自己的第一写法是对的 永远