集训队作业二分答案法的应用

1、二分上界（或）法的应用前言：在 题目的的信息学竞赛中，很多题目都令人无从下手，但如果先假定出法的应用。，问题就立刻迎刃而解。下面从几道例题谈谈二分例题一：草莓(noi2003)题意简述：所有草莓重量的和（1 i k）。定义：sumi 表示第 i 块草莓你的任务就是要把一片草莓田分割成k 块，且分割方案需要满足如下的条件：每一块中的草莓必然是通过触须直接或者间接和其他草莓相连接的；这种分割方案所对应的x 尽可能的大。最后输出你的分割方案和结果。算法分析：这是一道结果提交类问题，其中有 6 个数据都是树，现在行。对树进初一看，这题很难找到有效的模型，关键在于有的时候切出 sum 很大的一块反而不好

2、，因为题目中需要的是相对平均，因此，纯粹的贪心很难成立。试着稍微改变一下题目，假设题目要求求一种不小于x 的方法，我们该如何处理呢？很快有了头绪，首先通过宽度搜索建树，然后从叶子结点开始向上处理，如果有以某个结点为根的的权值和超过了 x，就将该结点以及它所在的作为通块，从图中删去。这样的做法一定是正确的，的结点给这个连通块显然是没有必要的。一因为 sum 一旦超过了x，如果把直进行这样的处理，如果割出了k 个连通块以上，则问题有解，否则问题无解。因为只要扫描一遍，因此这个问题的时间复杂度为 O(N)。既然已经可以在 O(N)的时间类解决上述子问题，那么能比较高效地求解原题呢？可以枚举每一个x

3、再加以判断，这样复杂度较高。比较好的方法是采用二分法，假如一个解在某个去间a，b，首先判断(a+b)/2 是否可行，如果可行，则枚举(a+b)/2+1,b，否则枚举a,(a+b)/2-1。那么，只需判断 logm次即可（其中m 为所有点的权值和）。如果不知道 x，可不可以用上面的方法呢？下部分的情况，所以无法在恰当的时候是否定的，因为你不知道剩的选择。复杂度分析：时间复杂度：O(NlogM)空间复杂度：O(N)备注：以上算法并不是严格的多项式算法，因为与权值有关，本题有多项式算法，但实际效果比以上算法略差，详细参加同学的。例题二：神秘的山(UVA10122)题意简述一座山有n 个山峰，有 n

4、个队员要攀登这些山峰，每个队员都选择不同的山攀登。队员必须从某整点开始攀登，线路为直线，且不能在空中飞_。下图就是一种可行方案每个队员的速度是一定的，现在要求上山峰。案，在最早的时候让全员都攀登算法分析：首先求出每个队员攀登到每个山峰所需要的时间，因为这些队员总是要在整点处攀登，用最简单的枚举来实现这一步：枚举一个点并加以判断。这样，很容易得到所需的信息。问题的关键是得到信息之后如何进行下一步的处理。显然，得到的是一个二分图，而每条边都值，二分图最佳匹配？最佳匹配所求的是总的权值和最小，而这题仅仅是要求权值最大的边最小，两者间有着一定的差异，而且并不容易相互转化，看来最佳匹配很难应用于在本题上

5、。先将问题简化，如果是求一个不超过q 的方案，有没有方法呢？有！而且相对很容易的，因为如果一个队员a 攀登山峰b 所需要的时间超过q，实际等价于这个队员无法攀登上山峰b，因此，就要在原先的二分图中删去有些无用的边， 重新构图，如果队员a 能在q 时间内攀登上山峰b，就在二分图a,b 两个顶点间连一条无向边。新图构造完成后，如果在新图中找到了一个完备匹配，则这可以作为一组可行方案，如果无法找到，则问题一定无解。在解决了这个简化后之后，回到原先的题目。首先，可以定一个上界，如果可以找到一个可行方案，则可以将上界降低，否则将向上增加，直到找到一个方案为止。这一步可以通过二分来实现，显然，最终的一定为

6、某个边的权，因此，需要对边权离散化，这样可以减少二分的次数。复杂度分析时间复杂度：O(N3logM)空间复杂度：O(N2)例题三：最大平均数问题(usaco)题意简述：给一个数列，在其中选出连续的一端数字（数字个数不小于 f），满足这一段的平均数最大。例如数列 3 4 2 3 4 5 6 ，f=3，则选择最后三个数字 4 5 6，它们的平均数是最大的。算法分析：如果用最简单的枚举，即使用部分和技术优化，时间复杂度也高达 O(N2)，无法让人接受。贪心法是否可行呢？经过尝试，几种贪心算法都被一一否决了，问题的关键是无法准确的知道一个数字对平均数影响有多大，因为平均数总是不短变化中的。既然这个无法

7、解决，不妨做一个大胆的尝试，如果把平均数固定，将问题转化为能否找到一段数字，使它们的平均数超过q，是否能找到有效算法呢？首先一组解，否则找到最初的 f 个数字，如果它们的平均数不小于 q，那么就得到了继续往后面扫描。填加下个数到当前数列中，如果数列开头的数字比q 小，则它的存在已经没有任何价值了，其从数列中删去。接着，下一个数加入数列，再对面前的数进行扫描。假设已经处理到了第 p个数，那么如果前p-m 个数的平均数小于q，则 3 4 2 3 4 5 6 为例进一步说明本算法。假设可以将他们删去。下面以平均数定为 4：可见，当平均数固定以后，可以很明确的知道一列数对平均数是否有贡献，那么，就可以

8、很轻松的作出决策了。回到原题可以不断枚举平均数，看在该平均数下是否能找到可行方案，数列加入数字新数列操作3 4 233 4 2 3开头的 3 小于 4，从数列中删去4 2 344 2 3 4开头数列不小于平均数，不作处理4 2 3 454 2 3 4 5开头数列 4 2 平均数小于 3，删去3 4 563 4 5 6平均数大于 4，结束如果可以找到，则将平均数向上增加，否则将平均数降低，之后进行同样的处理，直到确定。这一步通过二分来实现。复杂度分析：时间复杂度 O(NlogM)空间复杂度 O(N)备注事实上，本题有线形算法（参见远高于上述算法。），但实现较为烦琐，思考难度也小结：本题确定平均数

9、后，可以将一个数对平均数的影响由“相对”变为“绝对”。例题四： fence rail(usaco)题意简述：给 n 个物品和 m 个背包，每个物品都有体积，而背包也有相应的容积，要求将尽量多的物品放入背包中，求一种可行方案。算法分析：本题没有多项式算法，可以用搜索来解决。普通的想法是枚举每个物品分别放入哪些背包，显然这样做时间复杂度就太高了须对这一算法进行优化。但在原算法的基础上很难加入有效的优化。使用跟上面几道例题一样的分析方法，先将题目简化，如果题目求能否放入k 个物品，是不是就容易优化了呢？首先，肯定是尝试将最小的k 个物品放如背包中，这样就不必像以前那样盲目地选择物品了。可以算出这k

10、个物品的体积以及背包的剩余容积，如果剩余容积以放入全部物品，则继续搜索下去显然是没有意义的。从最大的物品开始按体积大小依次将物品放入背包（这样做是因为体积小的物品跟便于调整，有利于可以更快的找到方案），如果某个背包剩余的体积连当前最小的物品都放不下，则它的剩余容积从总剩余容积中减去。另外，还需要对物品进行“有序化”，如果两个物品体积相同，在搜索后一个物品的时候一定将它放一个物品的后面，这样可以减少搜索量。经过以上优化之后，程序就能很快判断出问题是否解了。回到原题，可以通过枚举k，判断是否能找到可行方案，再适当地增减k，这同样可以同二分实现。小结：本题通过二分可以使确定放入哪些物品，同时有利于加入一些优化。总结：二分法往往需要与其他一些算法相结合，且它的时间复杂度经常与题目中的某