《NOIP基础算法-贪心和分治》由会员分享，可在线阅读，更多相关《NOIP基础算法-贪心和分治（114页珍藏版）》请在金锄头文库上搜索。
1、NOIP基础算法分治与贪心,第五部分,分治策略,一、分治思想,分治法，又叫分治策略，顾名思义，分而治之。 它的基本思想：对于难以直接解决的规模较大的问题，把它分解成若干个能直接解决的相互独立的子问题，递归求出各子问题的解，再合并子问题的解，得到原问题的解。 通过减少问题的规模，逐步求解，能够明显降低解决问题的复杂度。,二、分治法的适用条件,能使用分治法解决的问题，它们一般具备以下几个特征： 该问题可分解成若干相互独立、规模较小的相同子问题； 子问题缩小到一定的程度就能轻易得到解； 子问题的解合并后，能得到原问题的解； 分治法在信息学竞赛中应用非常广泛，使用分治策略能生成一些常用的算法和数据结构
2、，如快排、最优二叉树、线段树等；还可以直接使用分治策略，解决一些规模很大、无法直接下手的问题。,三、分治的三步骤,分解：将要解决的问题分解成若干个规模较小的同类子问题； 解决：当子问题划分得足够小时，求解出子问题的解。 合并：将子问题的解逐层合并成原问题的解。,分治算法设计过程图,在划分问题时，可以采用递归策略，把一个大问题逐步分解成规模较小的子问题，直至可以直接求出子问题的解；再将子问题逐层合并，返回到顶层，得到原问题的解。 根据分治策略的划分原则，把原问题划分成多少个子问题才合适呢？各个子问题的规模应该多大才合适呢？ 一般来说，每次划分成2个子问题，每个子问题的规模差不多最合适。合并解时要
3、因题而异，有些问题递归分解完能直接得到原问题的解，有些问题需逐层合并，得到原问题的解。,四、分治的框架结构,procedure Divide() begin if(问题不可分)then/解决 begin 直接求解； 返回问题的解； end else begin 对原问题进行分治；/分解 递归对每一个分治的部分进行求解; /解决 归并整个问题，得出全问题的解; /合并 end end;,五、分治的典型应用,1、求最大值和最小值 2、求方程的根 3、二分查找 4、归并排序 5、快速幂 6、求解线性递推关系 7、棋盘覆盖问题 8、循环日程表问题 9、寻找最近点对,1、求最大值和最小值,例题1：给n个
4、数，求它们之中最大值和最小值，要求比较次数尽量小。,分析：假设数据个数为n,存放在数组a1n中。可以直接进行比较： minn:=a1;maxx:=a1; for i:=2 to n do if aimaxx then maxx:=ai; else if aiminn then minn:=ai; 使用这一算法，比较次数为2(n-1)。若n=10,则比较18次。,【方法2】分治策略 划分：把n个数均分为两半。即：划分点为d=(r1+r2)/2，两个区间为r1,d和d+1,r2。 递归求解：求左半的最小值min1 和最大值max1以及右半最小值min2和最大值max2。 合并：max1与max2比
5、较得到所有数的最大值为maxx； min1与min2比较得到所有数的最小值为minn。,procedure pd(r1,r2:integer;var maxx,minn:integer) begin var max1,min1,max2,min2,d:integer; if r1=r2 then begin maxx:=xr1; minn:=xr1;end else if r2=r1+1 then begin if xr2xr1 then begin maxx:=xr2;minn:=xr1;end else begin maxx:=xr1;minn:=xr2;end end else begi
6、n d:=(r1+r2)/2; pd(r1,d,max1,min1); pd(d+1,r2,max2,min2); if max1max2 then maxx:=max1;else maxx:=max2; if min1min2 then minn:=min1;else minn:=min2; end end,2、求方程的根,例题2：一元三次方程求解（NOIP2001） 【题目描述】有形如：ax3+bx2+cx+d=0这样的一个一元三次方程。给出该方程中各项的系数(a,b,c,d均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值=1。要求由小到大依
7、次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后4位。 【文件输入】输入仅一行，有四个数，依次为a、b、c、d 【文件输出】输出也只有一行，即三个根(从小到大输出) 【样例输入】1 -5 -4 20 【样例输入】-2.00 2.00 5.00,分析,如果精确到小数点后两位，可用简单枚举法：将x从-100.00 到100.00（步长0.01）逐一枚举，得到20000个 f(x)，取其值与0最接近的三个f(x)，对应的x即为答案。而题目已改成精度为小数点后4位，枚举算法时间复杂度将达不到要求。 直接使用求根公式，极为复杂。加上本题的提示给我们以启迪：采用二分法逐渐缩小根的范围，从而
8、得到根的某精度的数值。,分析,A.当已知区间(a,b)内有一个根时； 用二分法求根，若区间(a,b)内有根，则必有f(a)*f(b)b或f(a+b)/2)=0，则可确定根为(a+b)/2并退出过程； 、若f(a)*f(a+b)/2)0,则必然有f(a+b)/2)*f(b)0,根在(a+b)/2,b)中,对此区间重复该过程。 执行完毕,就可以得到精确到0.0001的根。,分析,B、求方程的所有三个实根 所有的根的范围都在-100至100之间，且根与根之差的绝对值=1。因此可知：在-100,-99、-99,-98、99，100、100，100这201个区间内，每个区间内至多只能有一个根。即：除区间
9、100，100外，其余区间a,a+1，只有当f(a)=0或f(a)*f(a+1)0时，方程在此区间内才有解。若f(a)=0 ，解即为a；若f(a)*f(a+1)0 ，则可以利用A中所述的二分法迅速出找出解。如此可求出方程的所有的解。,核心参考代码,procedure Divide(x1,x2:double) Begin var x0,y0,y1,y2:double; x0:=(x1+x2)div 2; y1:=cal(x1);y2:=cal(x2);y0:=cal(x0); if(x2-x11)then divide(x1,x0); if(y0*y21)then divide(x0,x2);
10、End;,3、归并排序,归并排序的基本思想：归并排序充分应用分治算法的策略，通过二分的思想，将n个数最终分成n个单独的有序数列，每个数列中仅有一个数字；再将相邻的两列数据合并成一个有序数列；再重复上面的合并操作，直到合成一个有序数列。按照分治三步法来说： （1）划分：把序列分成元素个数相等的两半； （2）递归求解：把两半分别排序； （3）合并：把两个有序表合成一个有序表；,分析,显然，前两部分是很容易完成的，关键在于如何把两个有序表合成一个。每次只需要把两个有序表中当前的最小元素加以比较，删除较小元素并加入合并后的新表中。,核心参考代码,procedure MergeSort(left,rig
11、ht:integer)/归并排序 begin if left=right then exit; /只有一个元素 mid:=(left+right)div 2; /找中间位 MergeSort(left,mid); /对左边归并 MergeSort(mid+1,right); /对右边归并 i:=left;j:=mid+1,p:=left; /合并左右 while(iaj)then begin tempp:=aj;inc(p);inc(j);end else begin tempp:=ai;inc(p);inc(i);end while(i=mid)do begin tempp:=ai;inc(
12、p);inc(i);end while(j=right)do begin tempp:=aj;inc(p);inc(i);end for i:=left to right do ai:=tempi; End;,【变形1】求逆序对数目,例题3：求“逆序对” 给定一整数数组A=(A1,A2,An), 若iAj,则就为一个逆序对。例如数组（3，1，4，5，2）的逆序对有,。问题是，输入n和A数组，统计逆序对数目。 数据范围：1=n=30000。,方法1：朴素算法,在看完试题以后，我们不难想到一个非常简单的算法穷举算法，即对数组中任意的两个元素进行判断，看它们是不是构成“逆序对”，因此这种算法的时间复
13、杂度为O(N2)。 c:=0; for i:=1 to n -1 do for j:=i+1 to n do if aiaj then c:=c+1; 时间效率不尽如人意 问题出现在哪里呢？,求逆序对的方法：,求逆序对有多种方法， 目前使用比较广泛且实现比较简单的主要有三种算法： 1、归并排序 2、线段树 3、树状数组,方法2：分治策略,采用二分法求解: 记数列ast,ed的逆序对数目为d(st,ed); mid=(st+ed)/2,则有： d(st,ed)=d(st,mid)+d(mid+1,ed)+F(st,mid,ed) 其中F(st,mid,ed)表示一个数取自ast,mid,另一个数
14、取自amid+1,ed所构成的逆序对数目。,和归并排序一样，划分和递归求解都好办，关键在于合并：如何求出i在左边，而j在右边的逆序对数目呢？统计的常见技巧是“分类”。我们按照j的不同把这些“跨越两边”的逆序对进行分类：只要对于右边的每个j，统计左边比它大的元素个数f(j)，则所有f(j)之和便是答案。 幸运的是，归并排序可以帮助我们“顺便”完成f(j)的计算：由于合并操作是从小到大进行排序的，当右边的aj复制到T中时，左边还没有来得及复制到T的那些数就是左边所有比aj大的数。此时累加器中加上左边元素个数mid-i+1即可。 即把“if(aiaj)then begin tempp:=aj;inc
15、(p);inc(j);end 改为“if(aiaj)then begin tot:=tot+mid-i+1;tempp:=aj;inc(p);inc(j);end,4、二分查找,【问题】给出从小到大排列的n个不同数a1an，试判断元素x是否出现在表中。,方法1：顺序查找。即一个一个进行寻找，时间复杂度为O(n)。这个方法并没有用到“n个数从小到大排列”这一个关键条件，因而时间效率低下。,方法2：二分查找,只需要比较log2n个元素。假设需要在aLar中查找元素x。 划分：检查某个元素am(Lx，那么元素只可能在aLam-1中 如果amx，那么元素只可能在am+1ar中。 合并：不需要合并。,实
16、现方法1：二分查找的递归实现,function bsh(L,r,x:integer):integer; Begin var m:integer; if Lr exit(-1); m:=(L+r)div 2; if am=x bsh:=m; else if amx then bsh:=bsh(L,m-1,x); else bsh:= bsh(m+1,r,x); End;,实现方法2：二分查找的非递归实现,function bsh(L,r,x:integer):integer; Begin var m:integer; while(Lx then r:=m-1 else L:=m+1; end bsh:=-1; /查找不成功 End;,【扩展1】
