这篇文章上次修改于 408 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

ACM程序课算法笔记8——二分答案

问题一：序列划分

给定n个正整数数组a，将这个序列从左到右划分成m段，使得每段至少有一个数；你需要让数字之和最大的那一段的数字和尽可能的小；求最大和最小的值。

根据题目分析，从正向思路来说，需要考虑如何划分，从而变得复杂。但我们如果有无限制的需求，从暴力的角度来看，能否通过枚举答案来获得结果呢？

如果有了答案，我们可以用贪心的思路，让每个子序列装最多个数的数。

让答案从1开始网上枚举，直到成立即可。以上复杂度为O(N2)

能否优化呢？从题目中可以发现，当中有很多无效的枚举，一旦减少枚举的数量，复杂度就可以降低。

那么我们可以选择二分答案，让答案值的枚举顺序和二分查找一样。此时的复杂度为O(NlogN)

典型的二分答案题通常有”最小值的最大值“，”最大值的最小值“。

至于为什么它们可以满足，是因为答案符合了满足二分的递增性。

例如上题，如果告诉你数字之和最大为T，那么你可以求出m段，显然随着T的变小，m会单调递增

给定n个正整数数组a和一个正整数k

一座高度为k的塔b[1…k]满足: b[1] x 2 <= b[2], b[2] x 2 <= b[3], b[3] x 2 <= b[4] …

你要从中选择一些数来叠很多座高度为k的塔,问最多能叠多少座塔。

依旧是二分答案，只不过不同在于如何验证，对于塔的堆叠，不应该一座一座塔的堆叠，应当对于k座塔，先把每座塔的最顶层放置，再放第二层，再放第三层。一旦不能堆叠，便无法叠。

给定n个正整数数组a 和 m个正整数数组b; 在n * m个a[i] + b[i] 中，找到第k小的数（不去重);

感想：即使我知道是二分答案，我也不好想出题解，此题提问的方式十分有参考价值，不能把二分答案的线索锁定在最小最大最大最小，f(x)[两个值的关系]的递增性才是更重要的

设f(x) 表示有多少对 i, j 满足 a[i] + b[j] <= x

找到最小的x，满足f(x) >= k;

接下来的思路是如何在已知x的情况下得到有几对。

首先将a, b进行排序。

对于已知x，对于数组a中的元素xa，所以数组b中可以和xa成对的个数就是b中小于等于x - xa。

此时就可以用二分查找b中小于x - xa的个数。

对于已知x，对于数组a中的元素xa，第一次找到b中满足数的位置，然后在xa变大的过程中，反向扫描满足条件b的个数，时间复杂度更低。