NOIP基础算法综合---分治与贪心.ppt

《NOIP基础算法综合---分治与贪心.ppt》由会员分享，可在线阅读，更多相关《NOIP基础算法综合---分治与贪心.ppt（83页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四部分第四部分 分治策略分治策略一、分治思想一、分治思想 分治法，又叫分治策略，顾名思义，分而治之。分而治之。 它的基本思想为：对于难以直接解决的规模较大的问题，把它分解成若干个能直接解决的相互独立的子问题，递归求出各子问题的解，再合并子问题的解，得到原问题的解。 通过减少问题的规模，逐步求解，能够明显降低解决问题的复杂度。 二、分治法的适用条件二、分治法的适用条件 能使用分治法解决的问题，它们一般具备以下几个特征： 该问题可以分解成若干相互独立、规模较小的相同子问题； 子问题缩小到一定的程度能轻易得到解； 子问题的解合并后，能得到原问题的解； 分治法在信息学竞赛中应用非常广泛，使用分治策略

2、能生成一些常用的算法和数据结构，如快排、最优二叉树、线段树等；还可以直接使用分治策略，解决一些规模很大、无法直接下手的问题。三、分治的三步骤三、分治的三步骤 分解：分解：将要解决的问题分解成若干个规模较小的同类子问题； 解决：当解决：当子问题划分得足够小时，求解出子问题的解。 合并：合并：将子问题的解逐层合并成原问题的解。分治算法设计过程图分治算法设计过程图 由分治法所得到的子问题与原问题具有相同的类型。如果得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出不用进一步细分就可求解的子问题。分治求解可用一个递归过程来表示。 要使分治算法效率高，关键在于

3、如何分割？一般地，出于一种平衡原则，总是把大问题分成K个规模尽可能相等的子问题，但也有例外，如求表的最大最小元问题的算法，当n6时，等分定量成两个规模为3的子表L1和L2不是最佳分割。一般来讲，都是2分为主。四、分治的框架结构四、分治的框架结构if(问题不可分问题不可分) 直接求解；直接求解； 返回问题的解；返回问题的解；else 对原问题进行分治；对原问题进行分治； 递归对每一个分治的部分求解递归对每一个分治的部分求解; 归并整个问题，得出全问题的解；归并整个问题，得出全问题的解； 例题例题1 1：给：给n n个实数，求它们之中最大值和最小值，要求个实数，求它们之中最大值和最小值，要求比较次

4、数尽量小。比较次数尽量小。分析：分析：假设数据个数为n,存放在数组a1.n中。可以直接进行比较： minn=a1;maxx=a1; for(i=2;imaxx)maxx=ai; else if(aixr1)maxx=xr2;minn=xr1; else maxx=xr1;minn=xr2; else d=(r1+r2)/2; pd(r1,d,max1,min1); pd(d+1,r2,max2,min2); if(max1max2)maxx=max1;else maxx=max2; if(min1min2)minn=min1;else minn=min2; 【思考试题思考试题】最大值最小化最大

5、值最小化 【问题描述问题描述】把一个包含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。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后4位。【文件输入文件输入】输入仅一行，有四个数，依次为a、b、c、d【文件输出文件输出】输出也只有一行，即三个根(从小到大输出)

6、【样例输入样例输入】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.A.当已知区间当已知区间(a,b)(a,b)内有一个根时；内有一个根时； 用二分法求根，若区间(a,b)内有根，则必有f(a)*f(b)b或f(a+b

7、)/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中所述的二分法迅速出找出解。如此可求出方程的所有的解。void divide(double x1,double x2) double x0,y0,y1,y2;

8、 x0=(x1+x2)/2; y1=cal(x1);y2=cal(x2);y0=cal(x0); if(x2-x10.00001&y1*y20) printf(%.4f ,(x2+x1)/2);return; if(y1*y01) divide(x1,x0); if(y0*y21) divide(x0,x2); 归并排序的基本思想：归并排序的基本思想：归并排序充分应用分治算法的策略，将n个数分成n个单独的有序数列，每个数列中仅有一个数字；再将相邻的两列数据合并成一个有序数列，每个数列中有2个数；再重复上面的合并操作，直到合成一个有序数列。按照分治三步法来说， 归并过程归并过程为： （1 1）划

9、分：）划分：把序列分成元素个数相等的两半； （2 2）递归求解：）递归求解：把两半分别排序； （3 3）合并：）合并：把两个有序表合成一个；分析分析 显然，前两部分是很容易完成的，关键在于如何把两个有关键在于如何把两个有序表合成一个序表合成一个。每次只需要把两个序列中当前的最小元素加以比较，删除较小元素并加入合并后的新表。int tempmaxn; /辅助空间辅助空间void MergeSort(int left,int right)/对区间对区间left-right进行归并排序进行归并排序 if(left= =right)return; /只有一个元素只有一个元素 mid=(left+rig

10、ht)/2; /找中间位找中间位 MergeSort(left,mid); /对左边归并对左边归并 MergeSort(mid+1,right); /对右边归并对右边归并 i=left,j=mid+1,p=left; /合并左右合并左右 while(i=mid&jaj) tempp+=aj+; else tempp+=ai+; while(i=mid)tempp+=ai+; while(j=right)tempp+=aj+; for(i=left;i=right;i+)ai=tempi; 【变形变形1 1】逆序对数目逆序对数目 例题：求例题：求“逆序对逆序对”。 给定一整数数组A=(A1,A2

11、,An), 若iAj,则就为一个逆序对。例如数组（3，1，4，5，2）的逆序对有,。问题是，输入n和A数组，统计逆序对数目。 数据范围：1=naj then c:=c+1; 时间复杂度为O(n2)采用二分法求解采用二分法求解:记数列记数列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,令一个数令一个数取自取自Amid+1,ed的逆序对数目。的逆序对数目。 和归并排序一样，划分和

12、递归求解都好办，关键在于合并：如何求出i在左边，而j在右边的逆序对数目呢？统计的常见技巧是“分类”。我们按照j的不同把这些“跨越两边”的逆序对进行分类：只要对于右边的每个j，统计左边比它大的元素个数f(j)，则所有f(j)之和便是答案。 幸运的是，归并排序可以帮助我们“顺便”完成f(j)的计算：由于合并操作是从小到大进行排序的，当右边的aj复制到T中时，左边还没有来得及复制到T的那些数就是左边所有比aj大的数。此时累加器中加上左边元素个数mid-i+1即可。 即把即把“if(aiaj) tempp+=aj+;”if(aiaj) tempp+=aj+;” 改为改为“if(aiaj)if(aiaj

13、)tot=tot+mid-tot=tot+mid-i+1;i+1;tempp+=aj+; ”tempp+=aj+; ”。 【问题描述问题描述】给出从小到大排列的n个不同数a0an-1，试判断元素x是否出现在表中。 方法方法1 1：顺序查找：顺序查找：方法是一个个寻找，时间复杂度为O(n)。这个方法并没有用到“n个数从小到大排列”这一个关键条件，因而时间效率低下。 只需要比较log2n个元素。假设需要在aLar中查找元素x。 划分：划分：检查某个元素am(L=mx，那么元素只可能在aLam-1中；如果amr)return -1; int m=(L+r)/2; if(am= x)return m;

14、 else if (amx) return bsearch(L,m-1,x); else return bsearch(m+1,r,x); int bsearch(int L,int r,int x) int m; while(Lx) r=m1;else L=m+1; return -1; /查找不成功查找不成功【扩展扩展1】二分查找求下界，即第一次出现的位置二分查找求下界，即第一次出现的位置 int Erfen(int L,int r,int x) int mid; while(Lr) mid=(L+r)/2; if(x=amid)r=mid; else L=mid+1; return L;

15、 【扩展扩展2】二分查找求上界，即最后一次出现位置的后一个二分查找求上界，即最后一次出现位置的后一个位置位置【思考题目思考题目】给出n个整数和m个询问，对于每个询问(a,b)，输出闭区间a,b内的整数c的个数。【思路点拨思路点拨】 先把所有的数据从小到大排序； 二分查找求下界，即第一次出现的位置low； 二分查找求上界，即最后一次出现位置的后一个位置high； 答案区间为：ans=high-low【变形变形1 1】查找等值点查找等值点 【问题描述问题描述】n个不同整数从小到大排序后放在数组A0An-1中，是否存在i，使得Ai=i？若存在，试找到此点。 【问题描述问题描述】计算计算a an n

16、%k%k ，n=10n=109 9。方法方法1：朴素算法。每次乘以：朴素算法。每次乘以a，时间复杂度时间复杂度O(n)。 int power(int a,int n) int x=1; for(i=1;ibpk;/输入三个数输入三个数 t=p; while(t!=0)len+;alen=t%2;t=t/2; /转为二进制转为二进制 ans=1; for(i=len;i=1;i-) /用二分法实现用二分法实现bp mod k ans=ans*ans%k; if(ai=1)ans=b%k*ans%k;/如果是奇数，就多乘如果是奇数，就多乘b coutans2)，其中f1=1,f2=1。现在请你求F

17、ibonacci数列的第n项。【文件输入文件输入】输入文件只有一行为一个整数n(1=n=231-1)。【文件输出文件输出】输出文件只有一行为一个整数，表示Fibonacci数列的第n项mod 32768的值。【样例输入样例输入】4【样例输出样例输出】3【数据范围数据范围】 对于20%的数据，1=n=1000 对于40%的数据，1=n=10000000 对于100%的数据，1=n=231-1 分析分析 枚举，肯定超时void precalc_fib(int n) f0=0;f1=1; for(int i=2;i=n;i+)fi=fi-1+fi-2; 可用倍增法在可用倍增法在O(logn)时间内求

18、出幂时间内求出幂(忽略高精度忽略高精度)一般情形一般情形【例题例题】比赛安排比赛安排【问题描述问题描述】设有2n(nn; m=1;a11=1;h=1; m=1n; /比赛总队数比赛总队数 while(h=m) /从一个球队开始构造从一个球队开始构造 for(i=1;i=h;i+) for(j=1;j=h;j+) aij+h=aij+h; /构造右上角方阵构造右上角方阵 ai+hj=aij+h; /构造左下角方阵构造左下角方阵 ai+hj+h=aij; /构造右下角方阵构造右下角方阵 h=h*2; 给定平面上n个点,找出其中的一对点的距离,使得在这n个点的所有点对中,该距离为所有点对中最小的。（

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

20、点，则由鸽笼原理易知至少有一个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/6d。这与d的意义相矛盾。也就是说矩形R中最多只有6个S中的点。 由于这种稀疏性质，对于P1中任一点p，P2中最多只有6个点与它构成最接近点对的候选者。序言 近年来的信息学竞赛中，经常需要求一个问题的可行解和最优解，这就是所谓的最优化问题。贪心法是求解这类问题的一种常用算法。在众多的算法中，贪心法可以算得上是最接近人们日常思维的一种算法，它在各级各类信

21、息学竞赛、尤其在一些数据规模很大的问题中发挥着越来越重要的作用。一、什么是贪心法一、什么是贪心法 贪心法是从问题的某一个初始状态出发，通过逐步构造最优解的方法向给定的目标前进，并期望通过这种方法产生出一个全局最优解的方法。贪心方法的基本思想 贪心是一种解题策略，也是一种解题思想 使用贪心方法需要注意局部最优与全局最优的关系，选择当前状态的局部最优并不一定能推导出问题的全局最优 利用贪心策略解题，需要解决两个问题：该题是否适合于用贪心策略求解如何选择贪心标准，以得到问题的最优解 【引例引例】在一个NM的方格阵中，每一格子赋予一个数（即为权），规定每次移动时只能向上或向右。现试找出一条路径，使其从

22、左下角至右上角所经过的权之和最大。 我们以23的矩阵为例：若按贪心策略贪心策略求解，所得路径为：1346；若按动态规划动态规划求解，所得路径为：12106。适用于贪心策略求解的问题的特点 适用于贪心策略求解的问题必须具有最优子结构的性质，但并不是所有具有最优子结构的问题都可以用贪心策略求解。因为贪心往往是盲目的，需要使用更理性的方法动态规划（例如“0-1背包问题”与“部分背包问题”）【问题问题1 1】部分背包问题部分背包问题 给定一个最大载重量为M的卡车和N种食品，有食盐，白糖，大米等。已知第i种食品的最多拥有Wi公斤，其商品价值为Vi元/公斤，编程确定一个装货方案，使得装入卡车中的所有物品总

23、价值最大。【分析分析】因为每一个物品都可以分割成单位块，单位块的利益越大，显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解答。 方法如下：先将单位块收益按从大到小进行排列，然后用循环从单位块收益最大的取起，直到不能取为止便得到了最优解。【问题问题2 2】0/10/1背包问题背包问题 给定一个最大载重量为M的卡车和N种动物。已知第i种动物的重量为Wi，其最大价值为Vi，设定M，Wi，Vi均为整数，编程确定一个装货方案，使得装入卡车中的所有动物总价值最大。【分析分析】按贪心法，有反例：设N=3,卡车最大载重量是100,三种动物A、B、C的重量分别是40,50,70,其对应的总价值分别是8

24、0、100、150。贪心策略与其他算法的区别贪心策略与其他算法的区别 1.1.贪心与递推：贪心与递推：与递推不同的是，贪心法中推进的每一步不是依据某一固定的递推式，而是当前看似最佳的贪心决策，不断的将问题归纳为更加小的相似的子问题。所以归纳、分析、选择正确合适的贪心策略，是正确解决贪心问题的关键。 2.2.贪心与动态规划：贪心与动态规划：与动态规划不同的是，贪心是鼠目寸光；动态规划是统揽全局。几个简单的贪心例子几个简单的贪心例子 例题例题1 1：删数问题：删数问题 键盘输入一个高精度的正整数n（n=240位）,去掉其中任意s个数字后剩下的数字按照原来的次序将组成一个新的正整数。编程对给定的n和

25、s,寻求一种方案,使得剩下组成的新数最小。 【样例输入】 178543 4 【样例输出】13 由于正整数n的有效位数最大可达240位，所以可以采用字符串类型来存储n。那么，应如何来确定该删除哪s位呢？是不是只要删掉最大的s个数字就可以了呢？ 为了尽可能地逼近目标，我们选取的贪心策略为：每一步总是选择一个使剩下的数最小的数字删去，即按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字，否则删除第一个递减区间的首字符。然后回到串首，按上述规则再删除下一个数字。重复以上过程s次，剩下的数字串便是问题的解了。 例题例题2 2：排队问题：排队问题 在一个食堂，有n个人排队买饭，每个人买饭需要的时间

26、为Ti，请你找出一种排列次序，是每个人买饭的时间总和最小。【思路点拨思路点拨】由题意可知，本题可以采用的贪心策略为：将n个人排队买饭的时间从小到大排序，再依次累加每人的买饭时间，即可得到最小的总和。由样例可知，排好序后的数据为(1,3,5,7,9,11)，每个人的买饭时间如下： T1=1 T2=T1+T2=1+3=4 T3=T2+T3=1+3+5=9 T4=T3+t4=1+3+5+7=16 T5=T4+T5=1+3+5+7+9=25 T6=T5+T6=1+3+5+7+9+11=36 总时间T=T1+T2+T3+T4+T5+T6=91 用反证法证明如下：假设一个不排好序的n个人也能得到最优答案，

27、比如把(1,3,5,7,9,11)中的3,5对调一下，得到的序列为(1,5,3,7,9,11)。对调后，3,5前后的1,7,9,11四个人的买饭时间不会有变化，关键的变化是3,5两个人。这时，5这个人的买饭时间为1+5，3这个人的买饭时间变为1+5+3，此时两个人的总买饭时间中，5被累加了2次，而原方案中是3被累加了2次，其他一样。由此，两者相比较，可知有序的序列能得到最优的方案。对于其他位置的改变可以采用同样的方法证明。用反证法证明时，关键是证明反例不成立，由此推出原方案是最优的。 有n个人排队到r个水龙头去打水，他们装满水桶的时间t1、t2.tn为整数且各不相等，应如何安排他们的打水顺序才

28、能使他们总共花费的时间最少？ 【例题例题3 3】打包打包 某工厂生产出的产品都要被打包放入正四棱柱的盒子内，所有盒子的高度为h，但地面尺寸不同，可以为 1x1、2x2、3x3、4x4、5x5、6x6。如下图所示。 这些盒子将被放入高度为h，地面尺寸为6x6的箱子中。为了降低运送成本，工厂希望尽量减少箱子的数量。如果有一个好算法，能使箱子的数量降到最低，这将给工厂节省不少的资金。请你编写一个程序。 贪心的经典应用贪心的经典应用 （一）、三个区间上的问题（一）、三个区间上的问题 1 1、选择不相交区间问题、选择不相交区间问题 2 2、区间选点问题、区间选点问题 3 3、区间覆盖问题、区间覆盖问题（

29、二）、两个调度问题（二）、两个调度问题 1 1、流水作业调度问题、流水作业调度问题 2 2、带限期和罚款的单位时间任务调度、带限期和罚款的单位时间任务调度贪心方法的推广 贪心与其它算法结合 搜索的最优化剪枝（ 生日蛋糕） 优化动态规划（ Peter的快餐店） 贪心方法与解题策略 最优方法不一定是最好方法 想不到最优解法就用较优解法贪心与其它算法结合：Peter的快餐店Peter最近在R市新开了一家快餐店。 该快餐店准备推出一种套餐，每套由A个汉堡、B个薯条和C个饮料组成。为了提高产量，Peter引进了N条生产线。所有生产线都可以生产汉堡、薯条和饮料，由于每条生产线一天能工作的时间是有限的、不同

30、的，而汉堡、薯条和饮料的单位生产时间又不同，Peter需要知道，怎样安排才能是一天中生产的套餐量最大。假设一天中汉堡、薯条和饮料的产量均不超过100个，且生产线总数小于等于10。贪心与其它算法结合用p1、p2、p3分别表示汉堡、薯条和饮料的单位生产时间，ti表示第i条生产线每天的生产时间，pi,j,k表示用前i条生产线生产j个汉堡、k个薯条的情况下，最多能生产的饮料数，ri,j,k表示用第i条生产线生产j个汉堡、k个薯条的情况下，最多能生产的饮料数，则pi,j,k=maxpi-1,j1,k1+ri,j-j1,k-k1 (j-j1)p1+(k-k1)p2ti)通过对该算法的时间复杂度分析，最坏的

31、情况下时间复杂度将达到109，是相当费时的。贪心与其它算法结合现在加入，用贪心方法作预处理 ： 首先计算出一天生产套数的上限值：min100 div A,100 div B,100 div C 接着，用贪心方法计算出这N条生产线可以生产的套数，并与上限比较，大于或等于则输出上限值并退出，否则再调用动态规划。因为贪心方法的代价很低，这里甚至可以使用多次贪心标准不同的贪心方法，取其最大值。 在运行动态规划的过程中，也可以每完成一阶段工作便与上限值进行比较，将贪心思想充分融入到动态规划过程中，这样以来，便可望在动态规划完成前提前结束程序。贪心方法小结贪心作为一种解题思路，虽然有时无法证明它的正确性，但在无法找到其他算法的时候，不失为一种好方法。并且，贪心与其他算法的结合，可以对其他算法起到优化作用。