这是《算法竞赛入门经典（第二版）》第八章笔记。
包括二分法，贪心，分治以及一些中级杂七杂八。
省略算法时间、排序等。

二分查找#

左开右闭区间与lower_bound, upper_bound#

一般二分法取中间点用 (l+r)/2，注意电脑整数除法的取整是向0取整，当 y>x 的时候，用 x+(y-x)/2 可以保证向下取整。
往常实现的二分查找:

int search(int *A, int l, int r, int v){  
	while(l<=r){  
		int m = (l+r)/2;  
		if(A[m]<v)  
			l = m+1;  
		else if(A[m]>v)  
			r = m-1;   //两边都要+1或-1  
		else  
			return m;  
	}  
	return l;  
}  

这样的结果是，如果有复数个那个值，无法确定找到的点是哪一个。如果没有那个值，则返回值是：把要查找的这个值放在返回值的位置（原本此位置的值和后面的值往后顺移一位），保证数组升序不变。

上面的区间是 [ l, r ]。

lower_bound, upper_bound

int lower_bound(int *A, int l, int r, int v)  
{  
	int m;  
	while(l<r){  
		m = l+(r-l)/2;  
		if(A[m]>=v) r = m;  
		else l = m+1;  
	}  
	return l;  
}  
  
int upper_bound(int *A, int l, int r, int v)  
{  
	int m;  
	while(l<r){  
		m = l+(r-l)/2;  
		if(A[m]<=v) l = m;  
		else r = m-1;  
	}  
	return l;  
}  

这里 l r 应该理解为左开右闭区间 [l, r)

用二分法化优化为判断#

二分法的 log2 使得它面对特别大的数也不怕。在任何有序枚举找解时（并且这些解也是有序、可以比大小的），都可以用二分法进行查找。
本质是化优化为暴力。

• 解在一定范围内
• 解本身有“大小”，可以比较、排序。

常见优化：最大值尽可能小
将包含 m 个正整数的序列划分为 k 个，使得 K 个子序列的序列和的最大值尽可能小。如果有多解，则第一个序列和尽可能小，还有多解，第二个序列和尽可能小，如此类推。

这是经典的化优化（最大值尽量小）为二分法判断的题目。首先化优化为暴力：从小到大遍历所有正整数，找到最小的能使所有子序列和都小于它的那个正整数。
又因为这里是有范围的，最大就是序列中所有正整数之和 M，所以可以用二分法直接在 0~M 间“猜数”查找——二分法。
判断正整数 x 是否满足条件：存在子序列划分使所有子序列和小于x。可以用贪心策略：因为所有都是正整数，序列越长越大，并且每个数都一定恰好属于一个序列，所以可以从左往右（从右往左也行）划分，每个子序列在不超过x的情况下尽可能长（一直到这个子序列允许的最右端，让后面的序列长度都为1），能这样划分出来，x就可以。
这里的二分实际上是个lower_bound。找到能满足条件的最小的 x。

最后在输出的时候，要求字典序，也可以用一个贪心策略：从右往左生成子序列，右边的子序列尽可能长（在最小 x 的约束下尽可能向左划分）。

递归与分治#

如果说动态规划还有五花八门的状态设计与状态转移，那么递归与分治一定是寻找子问题。

棋盘覆盖
2^k^ * 2^k^ 棋盘，只有一个黑色块，用三格的 L 形块去覆盖除了黑色块以外的，不能重叠，问覆盖方法。

基问题：2*2棋盘，除了那个黑色块，其它给一个 L 就行。
子问题：将棋盘一分为四，分治。
其中只有一个有原始黑块，另外三个：如果左上角分盘没有黑块，则假定右下角那个是黑的；如果是右上角，则假定左下角是黑的；如果是左下角，则假定右上角是黑的；如果是右下角，则假定左上角是黑的。这样三个没有黑块的分盘分治结束出来，刚好空出一个 L 形黑区域，可以放入一个L块。
分治+递归 ok。

巨人与鬼
图中有 N 个巨人 N 个鬼，每个巨人恰好对应一个鬼，并且，巨人和鬼的连线不能相交，求一个连接方法。

基问题：一个巨人一个鬼，直接相连。
递归：每次试图将整个图分为两部分，两边都是更少数量的巨人与鬼，并且两边各自的巨人=鬼。这样就是数量更少的相同问题，可以递归。
划分方法：找到位置最靠下的巨人，以此点为极点，正右为极轴，计算每个点与极点连线的角度，从小到大排序。依次按顺序走过每个点，一直到遇到一个鬼，此鬼左边的巨人数=鬼数（则右边必然也是巨人=鬼），则将此鬼与极点的巨人相连，此连线将问题一分为二。

贪心策略#

每一步寻找当前最优解。

装载（背包）问题#

找到优先级排序的量。
以下都是重要的原始模型，真正题目五花八门复杂得多，难矣。

1） n 个物体，每个重量 wi，总容量C，尽可能装多。
直接按照重量升序排列，优先装轻的。
如果是尽可能装得更重，就是经典的 0-1 背包变体，将在动态规划中提及。

2） n个物体，每个体积 wi，每个价值 vi，总容量C，每个物体可以任意分割，尽可能装最多价值。
按照每个物体单位体积的价值来排序，优先装单位体积价值高的。
如果不能分割，这就是经典的 0-1背包 问题，将在动态规划中记录。

3） n个人，每个人中 wi，每艘船最大载重C，每艘船最多乘坐2人，问怎么坐最少船。
按照体重升序排列，最轻的人和尽量重的人同乘（因为重的人难找伴），比这个“尽量重”还重的人只能一人一艘。剩下的此轻的人重复过程。

区间问题#

1） 最多不相交区间
按照区间结束位置升序排列，从左往右选，从能选的里（开始晚于上一个结束）选结束最早的。

2） 数个闭区间，选择尽可能少的点，使每个区间中至少一个点。
按照区间结束位置升序排列，从左往右判断，每当遇到一个没有被已有点覆盖（直接用所选的上一个点判断）的区间，选择这个区间的右端点。

3） 区间覆盖。选择尽可能少的区间覆盖某区间。
首先区间切割，切掉所有区间中在所需区间左界以左的部分，然后按照左端点升序排列，从所有左端点为所求区间左端点重合的小区间中选择右端点最右的。
然后更新所求区间的左端点为刚才所选区间的右端点，重复上面过程。

霍夫曼编码#

略。但这个贪心过程与由叶子构树的过程应留意。

中级杂七杂八：设计与优化策略#

构造#

直接构造解，无迹可寻。

翻转排序
从上到下一组数，能做的操作是选择一个位置，将此位置及以上的所有数翻转。设计一个方法进行排序，使从上到下为升序。

直接构造：每次要把最大值转到最下面，然后就可以忽略归位的最大值重复过程。
每次找到未被忽略位置中最大值的位置，以此为底翻转，最大值到顶上，然后整个翻转，最大值到底下归位。忽略已归位的最大值，重复。

中途相遇、双向搜索#

有时看似要遍历两边，但题目中可能有约束，确定一边，另一边也要有某种条件。可以只遍历一边，记录所有中途解，然后再遍历另一边，看是否和已有中途解对上。这样化乘积时间为加法。

和为0的四个数
给四个数集ABCD，各选一个使和为0. 几种选法

乍看暴力 n^4^，实际上，可以先遍历所有AB，求和，直接用map记录下所有解与对应的 ab 种类数，然后遍历 CD，求 -c-d，看map中是否有，如果有则解+1.这样双向求解为 n^2^log2n。

问题分解#

有些特殊问题可以分解为多个互不相干的小问题，这些小问题容易求解。

n车问题
在n*n棋盘上放 n 个车，使互相不吃。并且给n个矩形，使第 i 个车一定在第 i 个矩形中。

可见每行有且仅有一个车，每列有且仅有一个车。这样可以避免互相吃。
关于落在特定矩形的约束：只要行落在矩形的行范围内，列落在矩形的列范围内，就可以满足约束。
划分为两个互不相干的小问题：1n区间上有n个小区间，1n的位置上每个都要放一个车，第 i 个车落在第 i 个小区间中；有两个这样的小问题，两个的解分别是横纵坐标。——这就拆解了问题。

拆解来的小问题是区间相关的贪心策略。将所有小区间按照右端点升序排列，1~n棋盘从左往右放车，如果第 i 个位置被若干个小区间包含，那么这个位置上放这包含此位置的小区间中右端点最左的那个小区间编号的那个车。

子问题#

递归、分治、动态规划（部分）的基础。将问题划为若干阶段类似子问题的叠加。

买卖酒
直线上有n个等距村庄，每个村庄要么卖酒要么买酒，不能同时又买又卖。每个村庄的需求为 ai，正表示买酒，负表示卖酒。所有村庄供需平衡。将若干单位酒运送一个村庄间隔距离的耗费为酒的单位数，问耗费最小方案。

对于最左边的村庄，如果需要买 k 酒，一定避不开从次左边的村庄运来 k 酒的步骤，耗费+k。如果需要卖 k 酒，也一定避不开向次左边村庄运去 k 酒的步骤，耗费+k。
执行上一步骤后，相当于次左边村庄的需求量 +a最左边，耗费 +|a最左边|，最左边村庄的需求一定满足，忽略。
剩下的是相同意义的子过程。

扫描线#

扫描线是对暴力枚举的优化。以一定的规则扫描，使扫描过程中所需求的某个量可以随扫描很方便的更新，比如直线纵坐标随横坐标扫描增加斜率大小，避免更多一层甚至数层的枚举。

图形学的很多经典算法用到了扫描法，比如消隐算法等。

滑动窗口#

和扫描线类似，一般对应区间问题，可以在滑动过程中方便地更新某些本来需要枚举的量。

数据结构#

千奇百怪。

数形结合#

过于高端。