NOIP基础算法——贪心和分治pascal

1、NOIP基础算法分治与贪心,巴蜀中学 黄新军,:8080/bsoi,第四部分 分治策略,一、分治思想,分治(divide-and-conquer)就是“分而治之”的意思，其实质就是将原问题分成n个规模较小而结构与原问题相似的子问题；然后递归地解这些子问题，最后合并其结果就得到原问题的解。,二、分治法的适用条件,能使用分治法解决的问题，它们一般具备以下几个特征： 该问题可以分解成若干相互独立、规模较小的相同子问题； 子问题缩小到一定的程度就能轻易得到解； 子问题的解合并后，能得到原问题的解； 分治法在信息学竞赛中应用非常广泛，使用分治策略能生成一些常用的算法和数据结构，如快排、最优二叉树、线段树

2、等；还可以直接使用分治策略，解决一些规模很大、无法直接下手的问题。,三、分治的三步骤,分解：将要解决的问题分解成若干个规模较小的同类子问题； 解决：当子问题划分得足够小时，求解出子问题的解。 合并：将子问题的解逐层合并成原问题的解。,分治算法设计过程图,由分治法所得到的子问题与原问题具有相同的类型。如果得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出不用进一步细分就可求解的子问题。分治求解可用一个递归过程来表示。 要使分治算法效率高，关键在于如何分割？一般地，出于一种平衡原则，总是把大问题分成K个规模尽可能相等的子问题，但也有例外，如求表的最大最小

3、元问题的算法，当n6时，等分定量成两个规模为3的子表L1和L2不是最佳分割。一般来讲，都是2分为主。,四、分治的框架结构,procedure DIVIDE() begin if(问题不可分)then/解决 begin 直接求解； 返回问题的解； end else begin 对原问题进行分治；/分解 递归对每一个分治的部分求解; 归并整个问题，得出全问题的解;/合并 end end;,五、分治的典型应用,1、求最大值和最小值 2、非线性方程求根 3、二分查找 4、归并排序 5、快速幂 6、求解线性递推关系 7、棋盘覆盖问题 8、循环日程表问题 9、寻找最近点对,1、求最大值和最小值,例题1：给

4、n个实数，求它们之中最大值和最小值，要求比较次数尽量小。,分析：假设数据个数为n,存放在数组a1.n中。可以直接进行比较： minn:=a1;maxx:=a1; for i:=2 to n do if aimaxx then maxx:=ai; else if aixr1 then begin maxx:=xr2;minn:=xr1;end else begin maxx:=xr1;minn:=xr2;end end else begin d:=(r1+r2)/2; pd(r1,d,max1,min1); pd(d+1,r2,max2,min2); if max1max2 then maxx:

5、=max1;else maxx:=max2; if min1min2 then minn:=min1;else minn:=min2; end end,【思考试题】最大值最小化,【问题描述】把一个包含n个正整数的序列划分成m个连续的子序列(每个正整数恰好属于一个序列)。设第i个序列的各数之和为S(i)，你的任务是让所有的S(i)的最大值尽量小。例如序列1 2 3 2 5 4划分成3个序列的最优方案为1 2 3|2 5|4，其中S(1)=6，S(2)=7，S(3)=4，最大值为7；如果划分成1 2|3 2|5 4，则最大值为9；不如刚才的好。n=1。要求由小到大依次在同一行输出这三个实根(根与根

6、之间留有空格)，并精确到小数点后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位，枚举算法时间复杂度将达不到要求。 直接使用求根公式，极为复杂。加上本题的提示给我们以启迪：采用二分法逐渐缩小根的范围，从而得到根的某精度的数值,分析,A.

7、当已知区间(a,b)内有一个根时； 用二分法求根，若区间(a,b)内有根，则必有f(a)*f(b)b或f(a+b)/2)=0，则可确定根为(a+b)/2并退出过程； (2).若f(a)*f(a+b)/2)0,则必然有f(a+b)/2)*f(b)=1。因此可知：在-100,-99、-99,-98、99，100、100，100这201个区间内，每个区间内至多只能有一个根。即：除区间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中所述的二分法迅速出找出解。如此可求出方程的所

8、有的解。,核心参考代码,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); End;,3、归并排序,归并排序的基本思想：归并排序充分应用分治算法的策略，通过二分的思想，将n个数最终分成n个单独的有序数列，每个数列中仅有一个数字；再将相邻的两列数据合并成一个有序数列；再重复上面的合并操作，直到合成一个

9、有序数列。按照分治三步法来说， 归并过程为： （1）划分：把序列分成元素个数相等的两半； （2）递归求解：把两半分别排序； （3）合并：把两个有序表合成一个有序表；,分析,显然，前两部分是很容易完成的，关键在于如何把两个有序表合成一个。每次只需要把两个序列中当前的最小元素加以比较，删除较小元素并加入合并后的新表。,核心参考代码,tempmaxn; /辅助空间 procedure MergeSort(left,right:integer)/归并排序 begin if left=right then exit; /只有一个元素 mid:=(left+right)div 2; /找中间位 Merge

10、Sort(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(p);inc(i);end while(j=right)do begin tempp:=aj;inc(p);inc(i);end for i:=left to right do ai

11、:=tempi; End;,【变形1】逆序对数目,例题3：求“逆序对”。 给定一整数数组A=(A1,A2,An), 若iAj,则就为一个逆序对。例如数组（3，1，4，5，2）的逆序对有,。问题是，输入n和A数组，统计逆序对数目。 数据范围：1aj)then begin tempp:=aj;inc(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：顺序查找。方法是一个个寻找，时间复杂度

12、为O(n)。这个方法并没有用到“n个数从小到大排列”这一个关键条件，因而时间效率低下。,方法2：二分查找,只需要比较log2n个元素。假设需要在aLar中查找元素x。 划分：检查某个元素am(Lx，那么元素只可能在aLam-1中； 如果amr 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:intege

13、r; while(Lx then r:=m-1 else L:=m+1; end bsh:=-1; /查找不成功 End;,【扩展1】二分查找求下界，即第一次出现的位置 function Erfen(L,r,x:integer):integer; begin var mid:integer; while(Lr)do begin mid:=(L+r)div 2; if x=amid then r:=mid else L:=mid+1; end; Erfen:= L; end; 【扩展2】二分查找求上界，即最后一次出现位置的后一个位置,【思考题目】给出n个整数和m个询问，每次一个数字c,问整数c的

14、个数。,【思路点拨】 先把所有的数据从小到大排序； 二分查找求下界，即第一次出现的位置low； 二分查找求上界，即最后一次出现位置的后一个位置high； 答案区间为：ans=high-low,【变形1】查找等值点,【问题描述】n个不同整数从小到大排序后放在数组A1An中，是否存在i，使得Ai=i？若存在，试找到此点。,5、快速幂,【问题描述】计算an %k ，n2)，其中f1=1,f2=1。现在请你求Fibonacci数列的第n项。 【文件输入】输入文件只有一行为一个整数n(1=n=231-1)。 【文件输出】输出文件只有一行为一个整数，表示Fibonacci数列的第n项mod 32768的值

15、。 【样例输入】4 【样例输出】3 【数据范围】 对于20%的数据，1=n=1000 对于40%的数据，1=n=10000000 对于100%的数据，1=n=231-1,朴素算法，肯定超时,procedure Fib(n:integer) Begin var i:integer; f0:=0;f1:=1; for i:=2 to n do fi:=fi-1+fi-2; End;,先复习矩阵乘法 两个2*2矩阵相乘的公式为, 可用倍增法在O(logn)时间内求出幂(忽略高精度),一般情形,7、棋盘覆盖问题,分析,8、循环日程表问题,【例题】比赛安排 【问题描述】设有2n(n=6)个球队进行单循环

16、比赛,计划在2n -1天内完成，每个队每天进行一场比赛。设计一个比赛的安排，使在2n -1天内每个队都与不同的对手比赛。例如n=2时的比赛安排为： 队 1 2 3 4 比赛 1-2 3-4 第一天 1-3 2-4 第二天 1-4 2-3 第三天 【文件输入】一个整数n。 【文件输出】输出比赛安排表。 【样例输入】2 【样例输出】 1-2 3-4 1-3 2-4 1-4 2-3,初看此题，感觉无法下手，因为没有任何直接可用的算法和数据结构。 仔细分析，可以发现，将问题进行分解，能找出规律。 当n=1时，共有2个球队参赛，一天就可以比完。 当n=2时，共有4个球队，需比赛3天。从2个球队的比赛安排

17、表中可以看出，左上角与右下角对称，左下角与右上角对称，左下角的值是由左上角值加n得到的。,read(n); m:=1;a1,1:=1;h:=1; for i:=1 to n do m=2*m; /比赛总队数 while(h=m)do /从一个球队开始构造 begin for i:=1 to h do for j:=1 to h do begin ai,j+h:=ai,j+h; /构造右上角方阵 ai+h,j:=ai,j+h; /构造左下角方阵 ai+h,j+h:=ai,j; /构造右下角方阵 end; h:=h*2; end;,核心参考代码,9、寻找最近点对,给定平面上n个点,找出其中的一对点

18、的距离,使得在这n个点的所有点对中,该距离为所有点对中最小的。（n=60000）,分析,【问题简述】给定平面上n个点的坐标，找出其中欧几里德距离最近的两个点。 【方法1】枚举算法。需要枚举O(n2)个点对，每个距离的计算时间为O(1)，故总的时间复杂度为O(n2)。,有没有更好的算法呢？,【方法2】分治算法,先按照X坐标排序，把所有点划分成个数尽量相等的两部分，分别求最近点对，设距离分别为dL和dr。,合并：令d=mindL,dr，则跨越两边的点对中，只有下面的竖条中的才有可能更近。,需要检查竖条里的所有点对吗？,由d的意义可知，P2中任何2个S中的点的距离都不小于d。由此而来可以推出矩形R中

19、最多只有6个d/2*2/3*d的矩形(如下图所示)。,（反证法）若矩形R中有多于6个S中的点，则由鸽笼原理易知至少有一个d/2*2/3*d的小矩形中有2个以上S中的点。设U，V是这样2个点，它们位于同一小矩形中，则： (X(U)-X(V)2+(Y(U)-Y(V)2=(d/2)2+(d/2)2=25d2/36 因此，D(U,V)=5d/6从取1张牌放到(10 10 10 10）。,分析：,【试题分析】我们要使移动次数最少，就是要把浪费降至零。通过对具体情况的分析，可以看出在某相邻的两堆之间移动两次或两次以上，是一种浪费，因为我们可以把它们合并为一次或零次。 【思路点拨】如果你想到把每堆牌的张数减

20、去平均张数，题目就变成移动正数，加到负数中，使大家都变成0，那就意味着成功了一半！ 从第i堆移动-m张牌到第i+1堆，等价于从第i+1堆移动m张牌到第i堆,步数是一样的。 注意最左边的0和最右边的0不能算在内，如0,0,1,-3,4,0,-1,0,0,扩展1：,若题目中的纸牌排成一个环状，应如何处理呢？ 其中n=1000。,扩展2：,有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。求使所有人获得均等糖果的最小代价。 【数据规模】 对于30%的数据n=1000； 对于100%的数据n=1000000,贪心的经典应用,（一）、三个区间上的问题 1、

21、选择不相交区间问题 2、区间选点问题 3、区间覆盖问题 （二）、两个调度问题 1、流水作业调度问题 2、带限期和罚款的单位时间任务调度 （三）Huffman编码 （四）最优合并问题,1、选择不相交区间问题,给定n个开区间(ai, bi)，选择尽量多个区间，使得这些区间两两没有公共点。,【算法实现】首先按照b1=b2=si时，活动i与活动j相容。选择出由互相兼容的活动组成的最大集合。,2、区间选点问题,给定n个闭区间ai, bi，在数轴上选尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）。,【算法】：首先按照b1=b2=bn排序。每次标记当前区间的右端点X，并右移当前区间

22、指针，直到当前区间不包含X，再重复上述操作。,贪心策略：取最后一个。,例题6：种树（NOIP模拟试题）,一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号为1.n。每个块大小为一个单位尺寸并最多可种一棵树。每个居民想在门前种些树并指定了三个号码b,e,t。这三个数表示该居民想在b和e之间最少种t棵树。当然，b=e,居民必须保证在指定地区不能种多于地区被分割成块数的树，即要求t=s的bi的最大值即可。,例题7：区间（SDOI2005）,现给定n个闭区间ai,bi，1=i=n。这些区间的并可以表示为一些不相交的闭区间的并。你的任务就是在这些表示方式中找出包含最

23、少区间的方案。你的输出应该按照区间的升序排列。这里如果说两个区间a, b和c, d是按照升序排列的，那么我们有ab=c=d。 任务：读入这些区间，计算满足给定条件的不相交闭区间，并把这些区间按照升序输出。,练习试题：喷水装置,有一块草坪，长为L，宽为w；在它的中心线上装有n个点状的喷水装置，效果是让以它为中心半径为ri的圆被润湿，选择尽量少的喷水装置把整个草坪全部润湿。,1、流水作业调度问题,分析,2、带限期和罚款的单位时间任务调度,贪心方法的推广,贪心与其它算法结合 搜索的最优化剪枝（ 生日蛋糕） 优化动态规划（ Peter的快餐店） 贪心方法与解题策略 最优方法不一定是最好方法 想不到最优解法就用较优解法,贪心与其它算法结合,例题11：Peter的快餐店（贪心与动态规划） Peter最近在R市新开了一家快餐店。 该快餐店准备推出一种套餐，每套由A个汉堡、B个薯条和C个饮料组成。为了提高产量，Peter引进了N