NOIP基础算法——贪心和分治(1).ppt

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

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

2、叉树、线段树等；还可以直接使用分治策略，解决一些规模很大、无法直接下手的问题。三、分治的三步骤三、分治的三步骤n分解：分解：将要解决的问题分解成若干个规模较小的同类子问题；n解决：解决：当子问题划分得足够小时，求解出子问题的解。n合并：合并：将子问题的解逐层合并成原问题的解。分治算法设计过程图分治算法设计过程图n 在划分问题时，可以采用递归策略，把一个大问题逐步分解成规模较小的子问题，直至可以直接求出子问题的解；再将子问题逐层合并，返回到顶层，得到原问题的解。n 根据分治策略的划分原则，把原问题划分成多少个子问题才合适呢？各个子问题的规模应该多大才合适呢？n 一般来说，每次划分成2个子问题，每

3、个子问题的规模差不多最合适。合并解时要因题而异，有些问题递归分解完能直接得到原问题的解，有些问题需逐层合并，得到原问题的解。四、分治的框架结构四、分治的框架结构procedure Divide()begin if(问题不可分问题不可分)then/解决解决 begin 直接求解；直接求解； 返回问题的解；返回问题的解； end else begin 对原问题进行分治；对原问题进行分治；/分解分解 递归对每一个分治的部分进行求解递归对每一个分治的部分进行求解; /解决解决 归并整个问题，得出全问题的解归并整个问题，得出全问题的解; /合并合并 endend;n 例题例题1 1：给：给n n个数，求

4、它们之中最大值和最小值，要求比个数，求它们之中最大值和最小值，要求比较次数尽量小。较次数尽量小。分析：分析：假设数据个数为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);

5、if max1max2 then maxx:=max1;else maxx:=max2; if min1=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后4位。【文件输入文件输入】输入仅一行，有四个数，依次为a、b、c、d【文件输出文件输出】输出也只有一行，即三个根(从小到大输出)【样例输入样例输入】1 -5 -4 20【样例输入样例输入】-2.00 2.00 5.00n 如果精确到小数点后两位，可用简单枚举法：将x从-100.00 到100.00（步长0.01）逐一枚举，得到20000个 f(x)，取其值与0最接近的三个f(x)，对应的x即为答案。而题目已改

6、成精度为小数点后4位，枚举算法时间复杂度将达不到要求。n 直接使用求根公式，极为复杂。加上本题的提示给我们以启迪：采用二分法逐渐缩小根的范围，从而得到根的某精度的数值。n A.A.当已知区间当已知区间(a,b)(a,b)内有一个根时；内有一个根时；n 用二分法求根，若区间(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)=1。因此可知：在-100,-99、-99,-98、99，100、100，100这201个区间内，每个区间内至多只能有一个根。即：除区间100，1

7、00外，其余区间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-x10.00001 and y1*y20)then begin write(x2+x1)div 2:0:4);exit;end if(y

8、1*y01)then divide(x1,x0); if(y0*y21)then divide(x0,x2);End;n 归并排序的基本思想：归并排序的基本思想：归并排序充分应用分治算法的策略，通过二分的思想，将n个数最终分成n个单独的有序数列，每个数列中仅有一个数字；再将相邻的两列数据合并成一个有序数列；再重复上面的合并操作，直到合成一个有序数列。按照分治三步法来说： （1 1）划分：）划分：把序列分成元素个数相等的两半； （2 2）递归求解：）递归求解：把两半分别排序； （3 3）合并：）合并：把两个有序表合成一个有序表；分析分析n 显然，前两部分是很容易完成的，关键在于如何把两个有关键在

9、于如何把两个有序表合成一个序表合成一个。每次只需要把两个有序表中当前的最小元素加以比较，删除较小元素并加入合并后的新表中。procedure MergeSort(left,right: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(i

10、=mid and jaj)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:=tempi; End;【变形变形1 1】求逆序对数目求逆序对数目例题例题3 3：求：求“逆序对逆序对”n 给定一整数数组A=(A1,A2,An), 若iAj,则就

11、为一个逆序对。例如数组（3，1，4，5，2）的逆序对有,。问题是，输入n和A数组，统计逆序对数目。n 数据范围：1=naj then c:=c+1;n 时间效率不尽如人意时间效率不尽如人意.n 问题出现在哪里呢？问题出现在哪里呢？求逆序对的方法：求逆序对的方法：n 求逆序对有多种方法， 目前使用比较广泛且实现比较简单的主要有三种算法： 1、归并排序 2、线段树 3、树状数组n采用二分法求解采用二分法求解:n记数列记数列ast,ed的逆序对数目为的逆序对数目为d(st,ed);n mid=(st+ed)/2,则有：则有： d(st,ed)=d(st,mid)+d(mid+1,ed)+F(st,m

12、id,ed)n其中其中F(st,mid,ed)表示一个数取自表示一个数取自ast,mid,另一个另一个数取自数取自amid+1,ed所构成的逆序对数目。所构成的逆序对数目。n 和归并排序一样，划分和递归求解都好办，关键在于合并：如何求出i在左边，而j在右边的逆序对数目呢？统计的常见技巧是“分类”。我们按照j的不同把这些“跨越两边”的逆序对进行分类：只要对于右边的每个j，统计左边比它大的元素个数f(j)，则所有f(j)之和便是答案。n 幸运的是，归并排序可以帮助我们“顺便”完成f(j)的计算：由于合并操作是从小到大进行排序的，当右边的aj复制到T中时，左边还没有来得及复制到T的那些数就是左边所有

13、比aj大的数。此时累加器中加上左边元素个数mid-i+1即可。n 即把即把“if(aiaj)then begin tempp:=aj;inc(p);inc(j);endif(aiaj)then begin tempp:=aj;inc(p);inc(j);end n 改为改为“if(aiaj)then if(aiaj)then begin begin tot:=tot+mid-i+1;tot:=tot+mid-i+1;tempp:=aj;inc(p);inc(j);endtempp:=aj;inc(p);inc(j);end 【问题问题】给出从小到大排列的n个不同数a1an，试判断元素x是否出现

14、在表中。n 方法方法1 1：顺序查找。：顺序查找。即一个一个进行寻找，时间复杂度为O(n)。这个方法并没有用到“n个数从小到大排列”这一个关键条件，因而时间效率低下。n 只需要比较log2n个元素。假设需要在aLar中查找元素x。n 划分：划分：检查某个元素am(L=mx，那么元素只可能在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;function bsh(L,r,x:integer):integer;

15、 Begin var m:integer; while(Lx then r:=m-1 else L:=m+1; end bsh:=-1; /查找不成功查找不成功End; 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】二分查找求上界，即最后一次出现位置的后一个二分查找求上界，即最后一次出现位置的后一个位置位置【变形变形1 1

16、】：奇怪的函数：奇怪的函数 【问题描述问题描述】使得xx达到或超过n位数字的最小正整数x是多少？ 【文件输入文件输入】输入一个正整数n。 【文件输出文件输出】输出使得xx达到n位数字的最小正整数x。【变形变形2 2】：统计：统计 【问题描述问题描述】给你一个有n(n=100000)个整数的序列，接下来有m(m=10000)个询问，每个询问为一个整数，需要你输出在给出的序列中，此整数有多少个?【变形变形3 3】：查找等值点：查找等值点 【问题描述问题描述】n个不同整数从小到大排序后放在数组A1An中，是否存在i，使得Ai=i？若存在，试找到此点。 【问题问题】计算计算a an n mod kmo

17、d k的值的值 ，其中，其中n=10n=109 9。方法方法1：朴素算法。每次乘以：朴素算法。每次乘以a，时间复杂度时间复杂度O(n)。 function power(a,n:integer):integer; begin var x:integer; x:=1; for i:=1 to n do x:=x*a; power:=x; end;很明显，此程序要超时。很明显，此程序要超时。n划分：如果划分：如果n是偶数，则考虑是偶数，则考虑x=n div 2 否则考虑否则考虑x=(n-1) div 2n递归求解：计算递归求解：计算ax。n合并：如果合并：如果n是偶数，则是偶数，则an=(ax)2，

18、否则，否则an=(ax)2*a根据这个方法很容易写出程序：根据这个方法很容易写出程序：function power(a,n:integer):integer;Begin if n=0 begin power:=1;exit;end else if n mod 2=1 then /n为奇数的情况为奇数的情况 begin x:=power(a,(n-1)div 2); power:=(x*x)mod k*a)mod k; end else begin /n为偶数的情况为偶数的情况 x:=power(a,n div 2); power:=x*x mod k; end;End; read(a,b,k)

19、;/输入三个数输入三个数 t:=b; while t0 do begin inc(len);clen:=t mod 2;t:=t div 2;end;/转为二进制转为二进制 s:=1; for i:=len downto 1 do /用二分法实现用二分法实现ab mod k begin s:=s*s mod k; if ci=1 then s:=(a mod k)*s)mod k;/是奇数是奇数 end; writeln(s);/输出输出ab mod k【例题例题】Fibonacci数数【题目描述题目描述】Fibonacci数列定义为：fi=fi-2+fi-1 (i2)，其中f1=1,f2=1

20、。现在请你求Fibonacci数列的第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 n朴素算法O(n)，肯定超时procedure Fib(n:integer)begin var i:integer; f0:=0;f1:=1; for i:=2 to n do fi:=fi-

21、1+fi-2;end;n 可用倍增法在可用倍增法在O(logn)时间内求出幂时间内求出幂(忽略高精度忽略高精度)2212231212111110.11101110nnnnnnnnnnXFFXFFXFFFFFFFn若fi=fi-1+fi-2+fi-3，如何计算求出fn?【例题例题】比赛安排比赛安排【问题描述问题描述】设有2n(n=6)个球队进行单循环比赛,计划在2n -1天内完成，每个队每天进行一场比赛。设计一个比赛的安排，使在2n -1天内每个队都与不同的对手比赛。例如n=2时的比赛安排为： 队 1 2 3 4 比赛 1-2 3-4 第一天 1-3 2-4 第二天 1-4 2-3 第三天 【文

22、件输入文件输入】一个整数n。【文件输出文件输出】输出比赛安排表。【样例输入样例输入】2【样例输出样例输出】 1-2 3-4 1-3 2-4 1-4 2-3 分析分析1 1：递归形式实现：递归形式实现n 由于由于N个运动员要进行单循环比赛，且在个运动员要进行单循环比赛，且在N-1天内要结束全天内要结束全部比赛，经过分析，当且仅当部比赛，经过分析，当且仅当N为为2的整次幂时，问题才有的整次幂时，问题才有解，当然解是不唯一的。这样可以将运动员分成两组：解，当然解是不唯一的。这样可以将运动员分成两组： 1,2,N/2 和和 N/2+1,N/2+2,N。给第一组运动员安排一。给第一组运动员安排一个比赛日

23、程，得到一个个比赛日程，得到一个N/2阶的方阵阶的方阵A1；同时给第二组的；同时给第二组的运动员安排一个比赛日程，同样会得到一个运动员安排一个比赛日程，同样会得到一个N/2阶的一个方阶的一个方阵阵A2。考虑到比赛的性质，设定第。考虑到比赛的性质，设定第I个运动员在某一天的个运动员在某一天的比赛对手为第比赛对手为第K个运动员，则第个运动员，则第K个运动员在同一天的比赛个运动员在同一天的比赛对手必然是第对手必然是第I个运动员，即若有个运动员，即若有AI,J=K，则，则AK,J=I。因此原问题的解因此原问题的解(一个一个N阶方阵阶方阵)可以由分解后的两个子问题可以由分解后的两个子问题的解，合并起来。

24、同时每一个子问题又可以按照上述的二的解，合并起来。同时每一个子问题又可以按照上述的二分法分解下去，直至每个组中仅有分法分解下去，直至每个组中仅有2个运动员时为止。个运动员时为止。 procedure arrangment(K,N:integer);从K号运动员起的共N员运动员单循环比赛日程表的过程 begin if n=2 then 处理只有2名运动员的情况，递归终止条件 begin AK,0:=K;AK,1:=K+1; AK+1,0:=K+1; AK+1,1:=K; end else begin arrangment(K,N div 2); arrangment(K+N div 2,N di

25、v 2); 递归分解原问题与求解子问题 for i:=K to K+(N div 2) 1 do 合并子问题的解,构造原问题的解Ai,j for j:=(N div 2) to N-1 do Ai,j:=Ai+(N div 2),j-(N div 2); for i:=K+(N div 2) to K+N 1 do for j:=(N div 2) to N-1 do Ai,j:=Ai-(N div 2),j-(N div 2); end;end;方法方法1 1：递归形式实现：递归形式实现n 初看此题，感觉无法下手，因为没有任何直接可用的算法和数据结构。n 仔细分析，可以发现，将问题进行分解，

26、能找出规律。n 当n=1时，共有2个球队参赛，一天就可以比完。n 当n=2时，共有4个球队，需比赛3天。从2个球队的比赛安排表中可以看出，左上角与右下角对称，左下角与右上角对称，左下角的值是由左上角值加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; /构造右上角方阵构造右上角方阵 a

27、i+h,j:=ai,j+h; /构造左下角方阵构造左下角方阵 ai+h,j+h:=ai,j; /构造右下角方阵构造右下角方阵 end; h:=h*2; end; 【问题描述】给定平面上n (n=60000)个点,找出其中的一对点的距离,使得在这n个点的所有点对中,该距离为所有点对中最小的。 【问题简述问题简述】给定平面上n个点的坐标，找出其中欧几里德距离最近的两个点。 【方法方法1 1】枚举算法。枚举算法。需要枚举O(n2)个点对，每个距离的计算时间为O(1)，故总的时间复杂度为O(n2)。【方法方法2 2】分治算法分治算法 n 划分：先按照X坐标排序，把所有点划分成个数尽量相等的两部分，分别

28、求最近点对，设距离分别为dL和dr。 n 合并：令d=mindL,dr，则跨越两边的点对中，只有下面的竖条中的才有可能更近。n 从上往下看从上往下看, , 对于任何一个p, 另一侧可能与它组成更近的点对在一个正方形中, 它最多只有4个点(否则这个方格中会有距离比d小的点对)n 最坏情况(同一行的红蓝点几乎重合), 需要检查接下来的7个点(红蓝点混在一起)时间复杂度时间复杂度O(nlogn)n 分治是一种解题的策略，它的基本思想是：分治是一种解题的策略，它的基本思想是：“如果整个如果整个问题比较复杂，可以将问题分化，各个击破。问题比较复杂，可以将问题分化，各个击破。”n 分治包含分治包含“分分”

29、和和“治治”两层含义，如何分，分后如何两层含义，如何分，分后如何“治治”成为解决问题的关键所在成为解决问题的关键所在n 不是所有的问题都可以采用分治，只有那些能将问题分不是所有的问题都可以采用分治，只有那些能将问题分成与原问题类似的子问题，并且归并后符合原问题的性成与原问题类似的子问题，并且归并后符合原问题的性质的问题，才能进行分治质的问题，才能进行分治n 分治可进行二分，三分等等，具体怎么分，需看问题的分治可进行二分，三分等等，具体怎么分，需看问题的性质和分治后的效果。性质和分治后的效果。n 只有深刻地领会分治的思想，认真分析分治后可能产生只有深刻地领会分治的思想，认真分析分治后可能产生的预

30、期效率，才能灵活地运用分治思想解决实际问题。的预期效率，才能灵活地运用分治思想解决实际问题。n定义：贪心法是一种解决最优问题的策略。它是从问题的初始解出发，按照当前最佳的选择，把问题归纳为更小的相似的子问题，并使子问题最优，再由子问题来推导出全局最优解。n使用贪心方法需要注意局部最优与全局最优的关系，选择当前状态的局部最优并不一定能推导出问题的全局最优。n 【引例引例】在一个NM的方格阵中，每一格子赋予一个数值，规定每次移动时只能向上或向右。现试找出一条路径，使其从左下角至右上角所经过的数字之和最大。 n 我们以23的矩阵为例：若按贪心策略贪心策略求解，所得路径为：1346；若按动态规划动态规

31、划求解，所得路径为：12106。二、贪心策略的特点二、贪心策略的特点 n 1.1.贪心选择性质：贪心选择性质：算法中每一步选择都是当前看似最佳的选择，这种选择依赖于已做出的选择，但不依赖于未做的选择。n 2.2.最优子结构性质：最优子结构性质：算法中每一次都取得了最优解(即局部最优解)，要保证最后的结果最优，则必须满足全局最优解包含局部最优解。n 但并不是所有具有最优子结构的问题都可以用贪心策略求解。因为贪心往往是盲目的，需要使用更理性的方法动态规划（例如“0-1背包问题”与“部分背包问题”）【问题问题1 1】部分背包问题部分背包问题n 给定一个最大载重量为M的卡车和N种食品，有食盐，白糖，大

32、米等。已知第i种食品的最多拥有Wi公斤，其商品价值为Vi元/公斤，编程确定一个装货方案，使得装入卡车中的所有物品总价值最大。【分析分析】因为每一个物品都可以分割成单位块，单位块的利益越大，显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解答。 方法如下：先将单位块收益按从大到小进行排列，然后用循环从单位块收益最大的取起，直到不能取为止便得到了最优解。【问题问题2 2】0/10/1背包问题背包问题n 给定一个最大载重量为M的卡车和N种动物。已知第i种动物的重量为Wi，其最大价值为Vi，设定M，Wi，Vi均为整数，编程确定一个装货方案，使得装入卡车中的所有动物总价值最大。【分析分析】按贪心

33、法：每次选价格最大的装载。很明显有反例：设N=3,卡车最大载重量是100,三种动物A、B、C的重量分别是40,50,70,其对应的总价值分别是80、100、150。三、贪心策略与其他算法的区别三、贪心策略与其他算法的区别 n 1.1.贪心与递推：贪心与递推：与递推不同的是，贪心法中推进的每一步不是依据某一固定的递推式，而是当前看似最佳的贪心决策，不断的将问题归纳为更加小的相似的子问题。所以归纳、分析、选择正确合适的贪心策略，是正确解决贪心问题的关键。n 2.2.贪心与动态规划：贪心与动态规划：与动态规划不同的是，贪心是鼠目寸光；动态规划是统揽全局。四、贪心策略的证明四、贪心策略的证明n 贪心策

34、略能否适用，关键看在贪心的策略下，局部的最优解能否得到全局最优解。要看是否得到最优解，就要看贪心选择特征的证明了。常用的证明法有反证法和构造法。n 1.1.反证法：反证法：顾名思义，对于当前的贪心策略，否定当前的选择，看看是否能得到最优解，如果不能得到，说明当前贪心策略是正确的；否则，当前策略不正确，不可用。n 2.2.构造法：构造法：对于题目给出的问题，用贪心策略时，把问题构造成已知的算法或数据结构，以此证明贪心策略是正确的。五、几个简单的贪心例子五、几个简单的贪心例子 例题例题1 1：排队问题：排队问题 【问题描述】在一个食堂，有n个人排队买饭，每个人买饭需要的时间为Ti，请你找出一种排列

35、次序，使每个人买饭的时间总和最小。 【输入文件】输入文件共两行，第一行为n；第二行分别表示第1个人到第n个人每人买饭的时间T1,T2,Tn。 【输出文件】输出文件仅一行为买饭的时间总和。 【样例输入】 6 5 3 7 1 9 10 【样例输出】 90 【思路点拨思路点拨】假设取水的人按照1.n的顺序排列的，那么问题就转化为求以下公式的最小值： Total=T1+(T1+T2)+(T1+T2+T3)+.+(T1+T2+.+Tn)，对公式换个写法： Total=nT1+(n-1)T2+(n-2)T3.+2Tn-1+Tn 现在你是否发现一点什么呢？ 如果让T1=T2=T3=.=Tn，也就是把接水时间

36、少的人尽可能排在前面，总的等待时间就最少了。问题的本质就转变为把n个等待时间按照非递减的顺序排序，求出总和即可。 【证明】反证法。假设这种排列不正确，则交换T2和T3，有： Total=nT1+(n-1)T3+(n-2)T2.+2Tn-1+Tn 由于T2=Total，两者相比较，可知有序的序列能得到最优的方案。n 对于其他位置的改变可以采用同样的方法证明。用反证法证明时，关键是证明反例不成立，由此推出原方案是最优的。 【问题描述】有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得这n个人的平均等待时间最小。 【输入文件】输入文件共两行，第一行为n

37、；第二行分别表示第1个人到第n个人每人的接水时间T1,T2,Tn。 【输出文件】输出文件仅一行为最小的平均等待时间。 【样例输入】 6 5 3 7 1 9 10 【样例输出】 15 【思路点拨思路点拨】首先需要理解平均等待时间的概念。平均等待时间就是每个人的等待时间之和再除以n，因为n是个常数，所有等待时间之和最小也就等同于平均等待时间最小。 这样就转化为前面的问题了 【问题描述问题描述】有n个人排队到r个水龙头去打水，他们装满水桶的时间T1、T2,Tn为整数且各不相等，应如何安排他们的打水顺序才能使他们总共花费的时间最少？ 【文件输入文件输入】输入文件共计两行，第一行n，r(n=500,r=

38、75)，第二行为n个人打水所用的时间Ti (Ti从取3张牌放到(9 11 10 10)-从取1张牌放到(10 10 10 10）。 【文件输入文件输入】第一行为一个整数N(N堆纸牌,1=N=100)，第二行为n个用空格分开的整数，依次为A1 A2 An(N堆纸牌，每堆纸牌初始数，l=Ai=10000)。 【文件输出文件输出】所有堆均达到相等时的最少移动次数。 【样例输入样例输入】 4 9 8 17 6 【样例输出样例输出】3n 【试题分析试题分析】我们要使移动次数最少，就是要把浪费降至零。通过对具体情况的分析，可以看出在某相邻的两堆之间移动两次或两次以上，是一种浪费，因为我们可以把它们合并为一

39、次或零次。n 【思路点拨思路点拨】如果你想到把每堆牌的张数减去平均张数，题目就变成移动正数，加到负数中，最终使大家都变成0，那就意味着成功了一半！ n 从第i堆移动-m张牌到第i+1堆，等价于从第i+1堆移动m张牌到第i堆，步数是一样的。n 注意最左边的0和最右边的0不能算在内，如0,0,1,-3,4,0,-1,0,0 n若题目中的纸牌排成一个环状，应如何处理呢？n其中n=1000。n 有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。求使所有人获得均等糖果的最小代价。n 【数据规模数据规模】 对于30%的数据n=1000； 对于100%的数据n

40、=1000000 例题例题4:4:射击比赛（射击比赛（CEOI1997CEOI1997） n 我们假设射击的目标是一个由R*C(2RC 1000)个小方格组成的矩形网格。网格中每一列恰有2个白色的小方格和R-2个黑色的小方格。定义网格的行从顶至底编号为1R，列从左至右编号为1C。n 射击者可射击C次。在连续的C次射击中，若每列恰好有一个白色的方格被射中，且不存在无白色方格被射中的行，这样的射击才是正确的。问题是，如果存在正确的射击方法，则要求找到它。n 例如考虑如下目标：由上图可以看出，在每列中依次射中的行坐标为2,3,1,4。现在要求你编程计算出是否有正确的射击方法。n 根据题设条件，射击的

41、选择有2C种，符合要求的却很少。要解决问题，还需从正确的射击方法的特征入手。 【方法方法1 1】网络流算法网络流算法 n 我们将表示列的点编号为1到C，表示行的点编号为C+1到C+R，如果一个白色方格处在第i行第j列，那么从点j向点C+i连一条弧，弧的容量为1。再增设一个源点S，从点S往点1到C间各连一条弧，弧的容量为1，又设一个汇点T，从点C+1到点C+R向汇点T连一条弧，弧的容量为1，那么从源点S到汇点T求最大流，求出的最大流量即为最多可以射击到的行数。各条流的路线则描述了具体的射击方案。n 显然，如果用网络流求出的最大流量比R小，则问题无解，否则我们可以根据网络流的结果求出该二分图的具体

42、匹配方案。的连线流量为1的连线流量为0选择的射击格即为：(1,3), (2,1), (3,2), (4,4)S21432143Tu网络流算法经过优化，时间复杂度可以达到O(C*(n+4C+4R) u上述网络流算法虽然可以通过全部数据，但编程复杂度很高，而且极易出错，一不小心就会因为一个小错误影响整个程序。 1、统计所有行包含的白格数 2、从还没有射击格的行中选出一个白格数最少的 3、检查所选的行 （1）若所选行的白格数为0，则输出无解； （2）否则从所选行的白格中任选一个作为射击格，并将与该格同列的另一个白格所处行的白格数减1 4、返回到第2步，直到所有的行都有射击格。 5、若还有列没有选射击

43、格，则在该列任选一白格作为射击格即可n上面的贪心方法非常高效：n 时间复杂度为O(RC)，如果在程序中使用堆优化，时间复杂度将降为O(Rlog2C)。空间复杂度是线性的，而且非常容易实现。n 现在关键的问题就是如何证明它的正确性？用hi表示第i行的白格数。如果最开始的时候：n minhi=0：第i行已经没有办法找到可作为射击格的白格，那么问题只能无解。n minhi=1：那么第i行的这一个白格必须要作为射击格，否则将因第i行没有射击格而造成问题无解。n minhi2：那么在这一行任选一个白格,顶多只会造成剩余行中有一行h值为1,再处理那一行，最多也只会再造成剩余行中有一行h值为1，如此往复,将

44、保持h值为1的行数不超过1行，最后最坏的情况也是造成最后一行的h值为1,继续下去所有行就都已选取了射击格了。n 因此，如果原问题有解，该贪心方法一定能找到一种正确的方案。由此可以证明，此贪心方法是正确的。确定贪心标准。六、贪心的经典应用六、贪心的经典应用 （一）、三个区间上的问题（一）、三个区间上的问题 1 1、选择不相交区间问题、选择不相交区间问题 2 2、区间选点问题、区间选点问题 3 3、区间覆盖问题、区间覆盖问题（二）、两个调度问题（二）、两个调度问题 1 1、流水作业调度问题、流水作业调度问题 2 2、带限期和罚款的单位时间任务调度、带限期和罚款的单位时间任务调度（三）（三）Huff

45、manHuffman编码编码 （四）最优合并问题（四）最优合并问题 n 给定给定n n个开区间个开区间(a(ai i, b, bi i) )，选择尽量多个区间，使得，选择尽量多个区间，使得这些区间两两没有公共点。这些区间两两没有公共点。【算法实现算法实现】首先按照b1=b2=bn的顺序排序，依次考虑各个活动，如果没有和已经选择的活动冲突，就选；否则就不选。【正确性正确性】：如果不选b1，假设第一个选择的是bi，则如果bi和b1不交叉则多选一个b1更划算；如果交叉则把bi换成b1不影响后续选择。（一）、三个区间上的问题（一）、三个区间上的问题【样例输入样例输入】 6 3 4 6 7 1 3 2

46、5 5 6 4 7【样例输出样例输出】4 按照按照bi从小到大排序后的结果为：从小到大排序后的结果为： 1 3 3 4 2 5 5 6 4 7 6 7选择的区间为：选择的区间为： 1 3 3 4 5 6 6 7n 设有设有n n个活动，每个活动都要求使用同一资源，如个活动，每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动用这一资源。每个活动i i都有一个要求使用该资源都有一个要求使用该资源的起始时间的起始时间sisi和一个结束时间和一个结束时间fi fi，且，且sifisi=sjfi=sj或或fj=sifj=

47、si时，活时，活动动i i与活动与活动j j相容。选择出由互相兼容的活动组成的相容。选择出由互相兼容的活动组成的最大集合。最大集合。n 给定给定n n个闭区间个闭区间ai, biai, bi，在数轴上选尽量少的点，在数轴上选尽量少的点，使得每个区间内都至少有两个不同点（不同区间内使得每个区间内都至少有两个不同点（不同区间内含的点可以是同一个）。含的点可以是同一个）。【算法算法】：先按照所有区间的结束位置从小到大排序。从区间1到区间n进行循环，对于当前区间，若已选中的数不能覆盖它，则从区间末尾向前扫描，若当前数未选中出现，则将该数标记为已选中，直至使选中的数能满足该区间要求为止。【样例输入样例输

48、入】 4 4 3 6 3 6 2 4 2 4 0 2 0 2 4 7 4 7【样例输出样例输出】4 4【分析分析】0,1,2;2,3,4;3,4,5,6;4,5,6,70,1,2;2,3,4;3,4,5,6;4,5,6,7 ;2;2,1;2,1,4;2,1,4,6 ;2;2,1;2,1,4;2,1,4,6n上述算法的指导思想是在某一区间中排列越靠后的数对以后区间的影响越大，即它在以后区间出现的可能性越大，但未经严格数学证明。例题例题6 6：种树（：种树（NOIPNOIP模拟试题）模拟试题） n 一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号为1.n。每

49、个块大小为一个单位尺寸并最多可种一棵树。每个居民想在门前种些树并指定了三个号码b,e,t。这三个数表示该居民想在b和e之间最少种t棵树。当然b=e,居民必须保证在指定地区不能种多于地区被分割成块数的树，即要求t=s的的bi的最大值即可。的最大值即可。 【样例输入样例输入】 7 2 5 1 4 3 8 3 10 7 10 4 6 1 3 【样例输出样例输出】 1 4 3 10 按照按照bi从小到大排序后的结果为：从小到大排序后的结果为： 1 4 1 3 2 5 3 10 3 8 4 6 7 10例题例题7 7：区间（：区间（SDOI2005SDOI2005） n 现给定n个闭区间ai,bi，1=

50、i=n。这些区间的并可以表示为一些不相交的闭区间的并。你的任务就是在这些表示方式中找出包含最少区间的方案。你的输出应该按照区间的升序排列。这里如果说两个区间a, b和c, d是按照升序排列的，那么我们有ab=c=wj，这样替换显然会增加罚款的数额。因此，除上述安排方法以外的安排方法都不会使罚款的数额减少，可得上述方法得到的结果是最优的。七、贪心方法的推广七、贪心方法的推广n贪心与其它算法结合搜索的最优化剪枝（ 生日蛋糕）优化动态规划（ Peter的快餐店）n贪心方法与解题策略最优方法不一定是最好方法想不到最优解法就用较优解法贪心与其它算法结合贪心与其它算法结合：Peter的快餐店【问题描述】P