【题解】洛谷P1182数列分段Section II(二分答案详解)

题目

洛谷P1182数列分段Section II

题解

此题要用到二分法,但不是传统意义上的在单调序列中查找数值,而是二分答案转化为判定,比较抽象。首先,定义“如果能将数列分为m段,且每段长度小于等于sum,则称sum为合法值”,那么题中要求的就是最小的合法值。易证:越大的sum越容易合法,且存在分界值s,小于s的sum都不合法,大于等于s的sum都合法(s就是题目要求的值)。将合法值简称“1”,不合法值简称“0”。则对于从小到大的sum有如下序列:……0000011111……。若从小到大或从大到小一个个验证合法性,速度较慢,考虑二分。二分的左右指针为l和r,mid=(l+r)/2,它们都表示sum值。如果mid为合法值,则s在其左侧或是其本身,那么搜索范围可由[l,r]缩小为[l,mid];如果mid为非法值,则s在其右侧,范围由[l,r]缩小为[mid+1,r]。

下面讲如何进行合法性检测:贪心即可。从左往右分段,每一段尽量多,如果最后分的段数小于等于m,则合法。
0
此处的贪心是否需要进一步证明?x
Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年8月12日 下午9:51

【小白解析】
该题做法看似复杂,实则是枚举+二分查找的结合。(硬要说的话还有一丝数形结合的思想)
解法大刀阔斧地将“数字之和”比作“线段之长”,实际上是让题目的呈现更加形象:n条长度各异(长度即为每一个自然数)的线段按顺序拼成一长条,将其按不同方法分成m段,记录该分法下m条拼合线段中最大值。所有方法试验完后考察每种方法内的最大值,其中最小的“最大值”就是题目所要求的答案。
我们最初对于这个“最小的最大值”完全没有着手点,因此搬用最不辞辛劳的枚举法:不妨假设极端情况——该“最大值”是所有线段长度总和(实际题目中是总和的1/2),查看是否可行;若可行,动用贪心算法,变本加厉地减少“最大值”,再查看该值是否可行,直到不可行为止,现有的“最大值”既是所有值里最小的那一个。
不过逐一枚举的效率过低,不妨使用二分查找,可以最快定位“最小最大值”的所在位置。erfen()方法既是对二分查找的实现;第30行的条件判断是考察当前的“最大值”(即mid)是否可行,可行(check()==1)说明当前最大值还有减小的空间,则缩小二分查找的范围至左半边,恬不知耻地找更小的“最大值”;不可行(check()==0)说明当前最大值过小,则将范围调整至右半边,退而求其次。
check()方法的本质其实是从左往右拼线段:先拼第一条缝合线段,拼到该线段长度超过当前考察的“最大值”为止;若此时已拼了m段,即便这拼接上去的是最后一段,也没法把当前线段长度最大值控制在小于预期“最大值”的范围内,故而返回0,适当扩大预期;否则放下现有的缝合线段,以手中的材料(即16行的a[i])为起点,继续拼接。需要注意的是,如果某一段“材料”本身大于预期“最大值”,说明该预期根本不可行,同样返回0(12行)。如此一番操作下来,若没有出return 0,说明该预期“最大值”可行,则返回1(21行),接着贪得无厌。
*证明贪心合理在能力范围外了,望指教。