方法三
• 分治法。 • f[i,j]表示计算A[i..j]最大连续和。分以下三个步骤： • 1.划分问题：从中间一分为二分成[i,(i+j)shr 1]和[(i+j)shr 1+1,j]两部分； • 2.递归解决：递归解决f[i,(i+j)shr 1]和f[(i+j)shr 1+1,j]； • 3.合并问题：f[i,j:=max[f[i,(i+j)shr 1],f[(i+j)shr 1+1,j]]，除此 之外还要处理区间[i,j]中左边界<=(i+j)shr 1同时右边界 >=(i+j)shr 1+1的情况，可以采用枚举法。
f[i,(i+j)shr 1] f[(i+j)shr 1]+1,j
f[i,j]
• 答案为f[1,n]，时间复杂度T(n)=2*T(n/2)+n=O(nlgn)。
方法三程序
• function f(i,j:longint):longint; • var m,l,r,k:longint; • begin • if i=j then exit(a[i]); • m:=(i+j)shr 1; • f:=max(f(i,m),f(m+1,j)); • l:=-maxlongint; • for k:=m downto i do l:=max(l,s[m]-s[k-1]); • r:=-maxlongint; • for k:=m+1 to j do r:=max(r,s[k]-s[m]); • f:=max(f,l+r); • end;
方法五
• 此题可以不采用二分法来完成，时间复杂度 同样可以达到O((n+m)lgn)。 • 把问题中所涉及到的所有a-1和b合在一起排 序，排序后每个数i对应的num[i]是递增的，这 样在O(n)内完成所有的num[]。
方法六
• 离散化：把所有出现的数排序重新编号。 • 例如：
32 1 8 100 5 10 2 101
32 146 35 27
例4：第K小元素
• 输入n个整数和一个正整数k(1<=k<=n)输出 这些整数从小到大排序后的第k个(例如， k=1就是最小值)。n<=2*106。
方法一
• 快速排序、归并排序、堆排序时间复杂度 都是O(nlgn)，超时。
• 基数排序，虽然理论上是O(n)的，但常数
较大，超时。
方法三
• 由于n个整数是静态的，由始自终没有发生改变，所以 可以先对这n个数从小到大排序。 • 定义num(i)表示小于等于i的数的个数，则答案=num(b)num(a-1)。 • 计算num(b)和num(a-1)方法一样，都是采用二分法，拿 num[b]来说就是找出数组中<=b的最大下标。程序如下 ，其中left-1或right最终的值就是num[b]： • left:=1;right:=n; • while left<=right do begin • mid:=(left+right)shr 1; • if x[mid]<=b then left:=mid+1 else right:=mid-1; • end; • 时间复杂度为O((n+m)lgn)。
方法四
• 跟方法三一样，首先把n个数从小到大排序，跟方法三处理方法不同的是分 别求出两个下标： 1.low(a)表示>=a的最小下标；2.high(b)表示<=b的最大下标 答案就是high(b)-low(a)+1。其中high(b)跟方法三中的num(b)求法一样。 • 计算low[a]也是采用二分法，会因要求不同程序有所变动，程序如下,其中left 或right+1最终值就是low(a)： left:=1;right:=n; while left<=right do begin mid:=(left+right)shr 1; if x[mid]<a then left:=mid+1 else right:=mid-1; end; • 所以二分法写法也不固定，最终的答案也不固定要分析实际情况，只要分析 好right=left+1和left=right的情况就能保证不出错。 • 方法四时间复杂度为O((n+m)lgn)。
方法二
• 注意c*c在longint范围内，所以 c<=46340, 记录每一次乘法后的余数，在进行c+1个a相 乘后中间一定会出现重复余数，找出循环的 起点和终点，可以直接推算出答案。 • 假设起点为st,终点为en，y[i]记录a^i mod c 的值，则计算a^b mod c的程序如下： • p:=(b-st+1)mod(en-st+1); • if p=0 then p:=en-st+1; • writeln(y[st+p-1]); • st等于几？会固定一个值吗？为什么？
方法一
• • • • • • • • • • • 枚举：枚举i和j，再计算Ai+Ai+1+...+Aj。程序如下： max:=a[1]; for i:=1 to n-1 do begin for j:=i to n do begin s:=0; for k:=i to j do inc(s,a[k]); if s>max then max:=s end; end; writeln(max); 时间复杂度为O(n3)，当n较大时会超时。
方法五
• 初始化前缀和S[i]，a[i]+a[i+1]+...+a[j]=s[j]-s[i-1]。 • 枚举j，计算以a[j]结尾的最大连续子序列的和，起点i的范围 为1到j，s[j]已经确定，要使得s[i-1]尽可能小，s[j]-s[i-1]才 尽可能大，所以只要计算出s[0]到s[j-1]中的最小值即可。定 义minvalue[i]为s[0]到s[i]中的最小值,则 minvalue[i]=min(minvalue[i-1],s[i])，在O(n)内可以完成。 • 时间复杂度为O(n)。 • minvalue[0]:=0;s[0]:=0;ans:=a[1]; • for j:=1 to n do begin • s[j]:=s[j-1]+a[j];minvalue[j]:=min(minvalue[j-1],s[j]); • if s[j]-minvalue[j-1]>ans then ans:=s[j]-minvalue[j-1]; • end; • writeln(ans);
分治算法
分治思想
• 分治(divide-and-conquer)就是“分而治之”的意思，其 实质就是将原问题分成n个规模较小而结构与原问题相似 的子问题；然后递归地解这些子问题，最后合并其结果就 得到原问题的解。当n=2时的分治法又称二分法。 • 其三个步骤如下： 1.划分问题(Divide)：将原问题分成一系列子问题。 2.递归解决(Conquer)：递归地解各子问题。若子问题足 够小，则可直接求解。 3.合并问题(combine)；将子问题的结果合并成原问题的 解。 • 如快速排序、归并排序、二分查找都是采用分治思想。
方法二
• 用一个类似快速排序的方法，但不用完全排 序。用快排对L..R范围内的数排序，在划分 结束后，数组A[L..R]被分成A[L..j]和A[i,R]， 当i=j+2时中间可能还有一个数。因为这几段 是相对有序的，所以答案一定只会出现在其 中一段，对于另外的段就不用排序。 • 时间复杂度为O(n)。
例3：范围统计
• 给出n个整数xi和m个询问，对于每个询问 (a,b)，输出闭区间[a,b]内的整数xi的个数。
方法一
• 暴力枚举，对于每个询问都把n个整数枚举一遍
• 时间复杂度为O(nm)，会超时。
方法二
• 用num1[i]表示i的出现次数，num2[i]表示1到i 的出现次数总和,num2[i]=num2[i-1]+num1[i] • 对于询问a,b,输出num2[b]-num2[a-1] • 这种方法对于Xi不大时可以过，但如果 Xi很大 时，如达到10^9时空间就承受不了。
分治算法设计过程图
问题S
问题的分解
问题S1
问题S2
……
问题Si 子问题求 解
……
问题Sn
S1的解
S2的解
……
Si的解
……
Sn的解
子集解的合并
问题 S的解 S
例1：最大连续和
• 给出一个长度为n的序列A1,A2,...,An，求最大 连续和。换句话说，要求找到1<=i<=j<=n，
使得Ai+Ai+1+...+Aj尽量大。
方法一
• 枚举法 • 设f[x]=ax3+bx2+cx+d,从-100.00到100.00以 0.01的步长逐一枚举x并代入f[x]，找出最接近0 的三个f[x]，其对应的x就是答案。
• 当精度要求很高时会超时。
方法二
• 由于根和根之差的绝对值>=1,所以可以搜索区间[x,x+1](100<=x<=99)，求出对应的f[x]和f[x+1]，有以下三种情况： 1.f[x]=0，则确定x是方程的根； 2.f[x]*f[x+1]>0，则确定方程的根不在区间[x,x+1]内，设定 [x+1,x+2]为下一个搜索区间 3.f[x]*f[x+1]<0，则确定根在区间[x,x+1]内。 接下来采用二分法来求解，程序如下： x2 x1 mid x1:=x;x2:=x+1; while abs(x1-x2)>=0.001 do begin mid:=(x1+x2)/2; if f(x1)*f(mid)<0 then x2:=mid else x1:=mid; end; writeln(x1:0:2);
