vlambda博客
学习文章列表

我们这个系列叫随笔，意味着写起来会随意一些。如果是一定要写书评、或者是对书重难点归纳、或者是拓展的话可能就有些死板了，因此我用“随笔”作为这个系列的标题。而且我并不是想按照顺序一个个写下来，而是希望按照我自己的想法来写~希望大家能够喜欢。

看一本书，先看哪里？我觉得应该是先看序和前言的部分。其实有些内容还是比较重要的，比如它提到有些练习的答案可以在某个网址上查看。还告诉你看这本书之前至少得学会一些程序设计的基本知识和初等微积分的技巧。

希望你能先自行掌握第一章和第三章。同时先把第四章完整看一遍。

我们先看一个问题：来自于中国石油大学程序设计竞赛训练平台

2159: 【分治】折半查找法

题目描述

大魔导师培根曾经说过：“读书使人明智，读诗使人聪慧，演算使人精密，哲理使人深刻，伦理学使人有修养，逻辑修辞使人善辩。”由此可见书籍的重要性是不言而喻的。而与书籍天天打交道的图书管理员，更是夺天地之造化，吸日月之精华的“神之职业”

。据史料记载，魔法世界从古至今诞生的众多不平凡的人物中，有不少人都曾经做过“图书管理员”，如道家学派创始人老子，威软公司创始人比耳、少林藏经阁的扫地神僧等等。所以，作为以马虎自负出名的楚继光，在魔法学院的社会实践活动中又怎么会放过这“天将降大任于斯人也”的必经锻炼呢。但想成为一个合格的图书管理员并不容易，他必须能够在一排（10000以内）已按编号大小排好序的图书中，快速地按编号查找到某本书所在的位置。

输入

第一行是N，表示有N个元素，第二行是N个数，第三行是M表示要查找的数。

输出

一个数，即如找到该数，则输出位置，否则输出-1。

样例输入

32 4 64

样例输出

2

分析

题目大意其实就是在一堆已经排序好的数字中，找到目标数字所在的位置。样例只有3个数字，有些太少了。我们考虑如下的排列：

1 3 5 9 11 13 14 15 17 19 20 22

一共12个数字。我们记为数组a。那么很显然，因为是从小到大排序好的，所以我们能得出这样一个结论：对于数字a[i]而言，a[j]<a[i]（其中j<i）

方法其实很简单，我们使用分治思想。假如我们要查找数字19的位置。

1 3 5 9 11 13 14 15 17 19 20 22[1 3 5 9 11 13 ] [14 15 17 19 20 22]

我们把数组分成两组。然后判断中间的值。大家能发现19>13，因此13所在的那一部分肯定所有的数字都小于19，因此不满足条件。我们舍去这个部分。

[14 15 17 19 20 22][14 15 17] [19 20 22]

剩下的部分同样的分成两份。然后前面一半的最大值小于19，因此前面一半再次舍去。

[19 20 22][19 20] [22]

分成两份，这次我们发现有一点变化。前面一半的最大值是大于19的，后面一半的最小值大于19，因此后面一半所有数字全部都大于19，后面一半舍去。

最后我们分成[19] [20]两部分，显然前面一半是我们所要求的答案。

 int left=1,right=n; int mid=(left+right)/2; bool f=0; while(left<=right){ if(a[mid]>q) right=mid-1; else if(a[mid]<q) left=mid+1; else{f=1;break;} mid=(left+right)/2; }

二分查找是一个很经典的查找方式，核心运用到的是分治的思想。算法复杂度是O(log2N)。其中二分查找也可以用STL实现。但STL不是这一章节的核心内容因此不多加赘述，有兴趣的小伙伴可以自己翻阅资料查看。

二分的思想可以是很广泛的，不一定仅限于找数字这种情况。

再看一道题。来自洛谷

题目描述

对于给定的一个长度为N的正整数数列A_i 1∼N，现要将其分成 M（M≤N）段，并要求每段连续，且每段和的最大值最小。

关于最大值最小：

例如一数列4 2 4 5 1 要分成3 段。

将其如下分段：

[4 2][4 5][1]

第一段和为 6，第 2 段和为 9，第 3 段和为 1，和最大值为 9。

将其如下分段：

[4][2 4][5 1]

第一段和为 4，第 2 段和为 6，第 3 段和为 6，和最大值为 6。

并且无论如何分段，最大值不会小于 6。

所以可以得到要将数列4 2 4 5 1 要分成 3 段，每段和的最大值最小为 6。

输入格式

第 1 行包含两个正整数 N,M。

第 2 行包含 N 个空格隔开的非负整数 A_i，含义如题目所述。

输出格式

一个正整数，即每段和最大值最小为多少。

输入输出样例

输入 #1

5 34 2 4 5 1

输出 #1

6

说明/提示

N≤10^5  M≤N  Ai小于10^8，答案小于10^9

乍一看我们可能没思路，但注意到题目提示中写答案小于10^9。

我们考虑一个问题，假如我们猜测最小值为X。能不能判断这个值能不能符合题意？

这个问题瞬间就简单了起来，很容易能想到贪心的方法，只要让每段长度最大，然后判断段数是否小于M即可。

bool judge(int mid){ intans=0,tot=0; for(int i=1;i<=n;i++){ if(ans+a[i]>mid){ tot++;ans=a[i]; if(tot>=m)break; } else ans+=a[i]; } if(tot>=m) return 1; else return 0;}

之后我们能考虑到一个问题。这个寻找答案是不是和二分查找中的寻找数字是不是很像？

我们看假设会有1~10^9这么多可能的答案。其中答案很明显是从小到大排列的。而且我们发现，从某一个数字开始，每一个数字都将满足这个条件，或者说judge=1。

而在二分查找里面，数字是从小到大排列的，并且从某一个数字开始，每一个数字都满足≥寻找的数字这个条件。

在这里寻找答案完全可以用二分查找的路子来写。

因此我们可以二分答案来做这道题。

int main(){ scanf("%d%d",&n,&m); intl=-maxint,r=0; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); l=max(l,a[i]);r+=a[i]; } if(n==m){printf("%d\n",l);return 0;} while(l+1<r){ int mid=(l+r)/2; if(judge(mid)) l=mid; else r=mid; } if(!judge(r-1)) printf("%d\n",r-1); else printf("%d\n",r); return 0;}

分治是一个很关键的思想。我们了解了二分答案和二分查找之后，可能会会考虑：是不是只能二分？三分四分可不可以？

我们能推测出二分的时间复杂度是O(log2N),那么如果是三分呢？很明显是O(2*log3N)，仔细计算一下，三分会不会导致时间复杂度降低？

我们用二分是因为二分操作起来简单，而且也能达到我们所满意的复杂度级数了。当然有时候二分答案可能很难解决我们的问题：洛谷P3382

题目描述

如题，给出一个 N 次函数，保证在范围[l, r] 内存在一点 x，使得 [l, x] 上单调增，[x, r] 上单调减。试求出 x 的值。

输入格式

第一行一次包含一个正整数 N 和两个实数 l, r，含义如题目描述所示。

第二行包含 N + 1 个实数，从高到低依次表示该 N 次函数各项的系数。

输出格式

输出为一行，包含一个实数，即为 x 的值。若你的答案与标准答案的相对或绝对误差不超过 10^{-5}则算正确。

输入输出样例

输入 #1

3 -0.9981 0.51 -3 -3 1

输出 #1

-0.41421

说明/提示

对于 100% 的数据， 6≤N≤13，函数系数均在 [-100,100] 内且至多 15 位小数，∣l∣,∣r∣≤10 且至多 15 位小数。l≤r。

题目大意其实就是让我们求一个N次函数中的极点。

我们以题目中二次函数为例：l=-1.75   r=1.75

我们尝试用二分法，会发现二分法出问题了。因为这并不是一个从小到大排列的图形。但我们这个时候会想到另一种方法。

我们设置两个点。就让mid1=(l+r)/2  mid2=(mid1+r)/2。然后看看这两个点有什么特殊的地方。

很明显mid1>mid2。而且我们还知道l=r<mid2<mid1。这个顺序。我们能发现什么？

我们要找单调递增和单调递减的交点。那么很显然，答案所在的位置应该是代表最大的一个值。因此mid2~r之间应该是单调递减的，并且全部都不是答案。因此我们让r=mid2。

那么如果函数是这样子的，我们也能找到mid1和mid2的位置。

这个时候l<mid1<r<mid2。然后我们也能知道l~mid1是单调递增的，但是mid1很显然不是最大值，因此l~mid1不存在我想要的答案，全部舍去。令l=mid1。

当然情况还有很多很多种，这里就不一一列举了。但是我们很显然能发现一个规律：

当mid1<mid2时 l=mid1

当mid2<mid1时 r=mid2

回想起我们之前用的二分法，我们很容易能够得出下面的AC代码：

#include<bits/stdc++.h>#define N 25using namespace std;double l,r;long long n;double a[N];double q(double x){ doubleqq=0,pp=1; for(inti=n;i>=0;i--){ qq+=pp*a[i]*100000; pp*=x; } returnqq;}int main(){ cin>>n>>l>>r; for(inti=0;i<=n;i++) cin>>a[i]; while(l<=r-0.00000001){ doublel1=(l+r)/2; doublel2=(l1+r)/2; longlong ql1=floor(q(l1)*100000),ql2=floor(q(l2)*100000); if(ql1<ql2)l=l1; elseif(ql1>ql2) r=l2; elsel=l1,r=l2; } printf("%0.5lf",l); return0;}

大家看到了没有？在有单峰的情况下，我们不用二分法，而改用三分法。依旧能很高效率地得到我们想要的答案。

那么篇幅有限，这里对于分治算法我就只扩展二分查找、二分答案和三分的方法。这并不意味着分治只孕育了这三个算法，但这三个肯定是最基础的算法，当你理解了二分和三分的本质后，相信能对分治有进一步新的理解。也能更好地理解《算法导论》中第二章和第七章的内容了。

有问题发评论~谢谢大家支持！