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

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,存放在数组a1.n中。可以直接进行比较： 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 beg

6、in 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,ri

11、ght: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;i

15、nc(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

17、 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】二分查找求上界，即最后一次出现位置的后一个位置,【变形1】：奇怪的函数,【问题描述】使得xx达到或超过n位数字的最小正整数x是多少？ 【文件输入】输入一个正整数n。 【文件输出】输出使得xx

18、达到n位数字的最小正整数x。,【变形2】：统计,【问题描述】给你一个有n(n=100000)个整数的序列，接下来有m(m=10000)个询问，每个询问为一个整数，需要你输出在给出的序列中，此整数有多少个?,【变形3】：查找等值点,【问题描述】n个不同整数从小到大排序后放在数组A1An中，是否存在i，使得Ai=i？若存在，试找到此点。,5、快速幂,【问题】计算an mod k的值 ，其中n=109。,方法1：朴素算法。每次乘以a，时间复杂度O(n)。 function power(a,n:integer):integer; begin var x:integer; x:=1; for i:=1

19、to n do x:=x*a; power:=x; end; 很明显，此程序要超时。,方法2：分治算法,划分：如果n是偶数，则考虑x=n div 2 否则考虑x=(n-1) div 2 递归求解：计算ax。 合并：如果n是偶数，则an=(ax)2，否则an=(ax)2*a,方法2：分治算法,根据这个方法很容易写出程序： 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); pow

20、er:=(x*x)mod k*a)mod k; end else begin /n为偶数的情况 x:=power(a,n div 2); power:=x*x mod k; end; End;,方法3：用二进制实现快速幂计算,read(a,b,k);/输入三个数 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;

21、/是奇数 end; writeln(s);/输出ab mod k,6、求解线性递推关系,【例题】Fibonacci数 【题目描述】Fibonacci数列定义为：fi=fi-2+fi-1 (i2)，其中f1=1,f2=1。现在请你求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,朴素

22、算法O(n)，肯定超时,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)时间内求出幂(忽略高精度),扩展练习：,若fi=fi-1+fi-2+fi-3，如何计算求出fn?,7、棋盘覆盖问题,分析,8、循环日程表问题,【例题】比赛安排 【问题描述】设有2n(n=6)个球队进行单循环比赛,计划在2n -1天内完成，每个队每天进行一场比赛。设计一个比赛的安排，使在2n -1天内每个队都与不同

23、的对手比赛。例如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,分析1：递归形式实现,由于N个运动员要进行单循环比赛，且在N-1天内要结束全部比赛，经过分析，当且仅当N为2的整次幂时，问题才有解，当然解是不唯一的。这样可以将运动员分成两组： 1,2,N/2 和 N/2+1,N/2+2,N。给第一组运动员安排一个比赛日程，得到一个N/2阶的方阵A1；同时给第二组的运动员安排一个比赛日程，同样

24、会得到一个N/2阶的一个方阵A2。考虑到比赛的性质，设定第I个运动员在某一天的比赛对手为第K个运动员，则第K个运动员在同一天的比赛对手必然是第I个运动员，即若有AI,J=K，则AK,J=I。因此原问题的解(一个N阶方阵)可以由分解后的两个子问题的解，合并起来。同时每一个子问题又可以按照上述的二分法分解下去，直至每个组中仅有2个运动员时为止。,procedure arrangment(K,N:integer); 从K号运动员起的共N员运动员单循环比赛日程表的过程 begin if n=2 then 处理只有2名运动员的情况，递归终止条件 begin AK,0:=K;AK,1:=K+1; AK+1

25、,0:=K+1; AK+1,1:=K; end else begin arrangment(K,N div 2); arrangment(K+N div 2,N div 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);

26、 end; end;,方法1：递归形式实现,初看此题，感觉无法下手，因为没有任何直接可用的算法和数据结构。 仔细分析，可以发现，将问题进行分解，能找出规律。 当n=1时，共有2个球队参赛，一天就可以比完。 当n=2时，共有4个球队，需比赛3天。从2个球队的比赛安排表中可以看出，左上角与右下角对称，左下角与右上角对称，左下角的值是由左上角值加n得到的。,方法2：递推实现,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/构造其余三个方阵

27、 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 (n=60000)个点,找出其中的一对点的距离,使得在这n个点的所有点对中,该距离为所有点对中最小的。,分析,【问题简述】给定平面上n个点的坐标，找出其中欧几里德距离最近的两个点。 【方法1】枚举算法。需要枚举O(n2)个点对，每个距离的计算时间为O(1)，故总的时间复杂度为O(n2)。,有没有更好的算法

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

29、和“治”两层含义，如何分，分后如何“治”成为解决问题的关键所在 不是所有的问题都可以采用分治，只有那些能将问题分成与原问题类似的子问题，并且归并后符合原问题的性质的问题，才能进行分治 分治可进行二分，三分等等，具体怎么分，需看问题的性质和分治后的效果。 只有深刻地领会分治的思想，认真分析分治后可能产生的预期效率，才能灵活地运用分治思想解决实际问题。,第六部分,贪心策略,一、贪心策略的基本思想,定义：贪心法是一种解决最优问题的策略。它是从问题的初始解出发，按照当前最佳的选择，把问题归纳为更小的相似的子问题，并使子问题最优，再由子问题来推导出全局最优解。 使用贪心方法需要注意局部最优与全局最优的关

30、系，选择当前状态的局部最优并不一定能推导出问题的全局最优。,【引例】在一个NM的方格阵中，每一格子赋予一个数值，规定每次移动时只能向上或向右。现试找出一条路径，使其从左下角至右上角所经过的数字之和最大。 我们以23的矩阵为例：,若按贪心策略求解，所得路径为：1346； 若按动态规划求解，所得路径为：12106。,二、贪心策略的特点,1.贪心选择性质：算法中每一步选择都是当前看似最佳的选择，这种选择依赖于已做出的选择，但不依赖于未做的选择。 2.最优子结构性质：算法中每一次都取得了最优解(即局部最优解)，要保证最后的结果最优，则必须满足全局最优解包含局部最优解。 但并不是所有具有最优子结构的问题

31、都可以用贪心策略求解。因为贪心往往是盲目的，需要使用更理性的方法动态规划（例如“0-1背包问题”与“部分背包问题”）,【问题1】部分背包问题,给定一个最大载重量为M的卡车和N种食品，有食盐，白糖，大米等。已知第i种食品的最多拥有Wi公斤，其商品价值为Vi元/公斤，编程确定一个装货方案，使得装入卡车中的所有物品总价值最大。,【分析】因为每一个物品都可以分割成单位块，单位块的利益越大，显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解答。 方法如下：先将单位块收益按从大到小进行排列，然后用循环从单位块收益最大的取起，直到不能取为止便得到了最优解。,【问题2】0/1背包问题,给定一个最大载重

32、量为M的卡车和N种动物。已知第i种动物的重量为Wi，其最大价值为Vi，设定M，Wi，Vi均为整数，编程确定一个装货方案，使得装入卡车中的所有动物总价值最大。,【分析】按贪心法：每次选价格最大的装载。很明显有反例：设N=3,卡车最大载重量是100,三种动物A、B、C的重量分别是40,50,70,其对应的总价值分别是80、100、150。,三、贪心策略与其他算法的区别,1.贪心与递推：与递推不同的是，贪心法中推进的每一步不是依据某一固定的递推式，而是当前看似最佳的贪心决策，不断的将问题归纳为更加小的相似的子问题。所以归纳、分析、选择正确合适的贪心策略，是正确解决贪心问题的关键。 2.贪心与动态规划

33、：与动态规划不同的是，贪心是鼠目寸光；动态规划是统揽全局。,四、贪心策略的证明,贪心策略能否适用，关键看在贪心的策略下，局部的最优解能否得到全局最优解。要看是否得到最优解，就要看贪心选择特征的证明了。常用的证明法有反证法和构造法。 1.反证法：顾名思义，对于当前的贪心策略，否定当前的选择，看看是否能得到最优解，如果不能得到，说明当前贪心策略是正确的；否则，当前策略不正确，不可用。 2.构造法：对于题目给出的问题，用贪心策略时，把问题构造成已知的算法或数据结构，以此证明贪心策略是正确的。,五、几个简单的贪心例子,贪心策略,例题1：排队问题,【问题描述】在一个食堂，有n个人排队买饭，每个人买饭需要

34、的时间为Ti，请你找出一种排列次序，使每个人买饭的时间总和最小。 【输入文件】输入文件共两行，第一行为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=Total，两者

35、相比较，可知有序的序列能得到最优的方案。 对于其他位置的改变可以采用同样的方法证明。用反证法证明时，关键是证明反例不成立，由此推出原方案是最优的。,问题推广1：排队打水问题,【问题描述】有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得这n个人的平均等待时间最小。 【输入文件】输入文件共两行，第一行为n；第二行分别表示第1个人到第n个人每人的接水时间T1,T2,Tn。 【输出文件】输出文件仅一行为最小的平均等待时间。 【样例输入】 6 5 3 7 1 9 10 【样例输出】 15,【思路点拨】首先需要理解平均等待时间的概念。平均等待时间就是每个人

36、的等待时间之和再除以n，因为n是个常数，所有等待时间之和最小也就等同于平均等待时间最小。 这样就转化为前面的问题了,问题推广2：排队打水问题,【问题描述】有n个人排队到r个水龙头去打水，他们装满水桶的时间T1、T2,Tn为整数且各不相等，应如何安排他们的打水顺序才能使他们总共花费的时间最少？ 【文件输入】输入文件共计两行，第一行n，r(n=500,r=75)，第二行为n个人打水所用的时间Ti (Ti=100)； 【文件输出】输出文件只有一行为n个人打完水的最少总共花费时间。 【样例输入】 3 2 1 2 3 4 【样例输出】13,例题2：打包,某工厂生产出的产品都要被打包放入正四棱柱的盒子内，

37、所有盒子的高度为h，但地面尺寸不同，可以为 1x1、2x2、3x3、4x4、5x5、6x6。如下图所示。,这些盒子将被放入高度为h，地面尺寸为6x6的箱子中。为了降低运送成本，工厂希望尽量减少箱子的数量。如果有一个好算法，能使箱子的数量降到最低，这将给工厂节省不少的资金。请你编写一个程序。,分析,分析,例题3:均分纸牌（NOIP2002）,有N堆纸牌，编号分别为 1,2,N。每堆上有若干张，但纸牌总数必为N的倍数。可以在任一堆上取若于张纸牌，然后移动。 移牌规则为：在编号为1堆上取的纸牌，只能移到编号为2的堆上；在编号为N的堆上取的纸牌，只能移到编号为N-1的堆上；其他堆上取的纸牌，可以移到相

38、邻左边或右边的堆上。 现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。 例如 N=4，4 堆纸牌数分别为：98176 移动3次可达到目的：从取4张牌放到(9 8 13 10)-从取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 【样例输出】3,分析：,【试题分析】我们要使移动次数最少，就是要把浪费降

39、至零。通过对具体情况的分析，可以看出在某相邻的两堆之间移动两次或两次以上，是一种浪费，因为我们可以把它们合并为一次或零次。 【思路点拨】如果你想到把每堆牌的张数减去平均张数，题目就变成移动正数，加到负数中，最终使大家都变成0，那就意味着成功了一半！ 从第i堆移动-m张牌到第i+1堆，等价于从第i+1堆移动m张牌到第i堆，步数是一样的。 注意最左边的0和最右边的0不能算在内，如0,0,1,-3,4,0,-1,0,0,扩展1：（NOIP模拟试题）,若题目中的纸牌排成一个环状，应如何处理呢？ 其中n=1000。,扩展2：（2011重庆省选）,有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人

40、传递糖果。每人每次传递一个糖果代价为1。求使所有人获得均等糖果的最小代价。 【数据规模】 对于30%的数据n=1000； 对于100%的数据n=1000000,例题4:射击比赛（CEOI1997）,我们假设射击的目标是一个由R*C(2RC 1000)个小方格组成的矩形网格。网格中每一列恰有2个白色的小方格和R-2个黑色的小方格。定义网格的行从顶至底编号为1R，列从左至右编号为1C。 射击者可射击C次。在连续的C次射击中，若每列恰好有一个白色的方格被射中，且不存在无白色方格被射中的行，这样的射击才是正确的。问题是，如果存在正确的射击方法，则要求找到它。,例如考虑如下目标：由上图可以看出，在每列中

41、依次射中的行坐标为2,3,1,4。现在要求你编程计算出是否有正确的射击方法。,根据题设条件，射击的选择有2C种，符合要求的却很少。要解决问题，还需从正确的射击方法的特征入手。,【方法1】网络流算法,我们将表示列的点编号为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求最大流，求出的最大流量即为最多可以射击到的行数。各条流的路线则描述了具体的射击方案。 显然，如果用网络流求出的

42、最大流量比R小，则问题无解，否则我们可以根据网络流的结果求出该二分图的具体匹配方案。,红色的连线流量为1 蓝色的连线流量为0 选择的射击格即为： (1,3), (2,1), (3,2), (4,4),网络流算法经过优化，时间复杂度可以达到O(C*(n+4C+4R) 上述网络流算法虽然可以通过全部数据，但编程复杂度很高，而且极易出错，一不小心就会因为一个小错误影响整个程序。,【方法二】贪心方法 1、统计所有行包含的白格数 2、从还没有射击格的行中选出一个白格数最少的 3、检查所选的行 （1）若所选行的白格数为0，则输出无解； （2）否则从所选行的白格中任选一个作为射击格，并将与该格同列的另一个白

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

44、余行中有一行h值为1,再处理那一行，最多也只会再造成剩余行中有一行h值为1，如此往复,将保持h值为1的行数不超过1行，最后最坏的情况也是造成最后一行的h值为1,继续下去所有行就都已选取了射击格了。 因此，如果原问题有解，该贪心方法一定能找到一种正确的方案。由此可以证明，此贪心方法是正确的。确定贪心标准。,六、贪心的经典应用,（一）、三个区间上的问题 1、选择不相交区间问题 2、区间选点问题 3、区间覆盖问题 （二）、两个调度问题 1、流水作业调度问题 2、带限期和罚款的单位时间任务调度 （三）Huffman编码 （四）最优合并问题,1、选择不相交区间问题,给定n个开区间(ai, bi)，选择尽

45、量多个区间，使得这些区间两两没有公共点。,【算法实现】首先按照b1=b2=bn的顺序排序，依次考虑各个活动，如果没有和已经选择的活动冲突，就选；否则就不选。,贪心策略：取满足条件的第一个区间；,【正确性】：如果不选b1，假设第一个选择的是bi，则如果bi和b1不交叉则多选一个b1更划算；如果交叉则把bi换成b1不影响后续选择。,（一）、三个区间上的问题,【样例输入】 6 3 4 6 7 1 3 2 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 7,例题5：活动安排,设有n个活动，

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

47、 4 3 6 2 4 0 2 4 7 【样例输出】4,【分析】0,1,2;2,3,4;3,4,5,6;4,5,6,7 ;2;2,1;2,1,4;2,1,4,6,上述算法的指导思想是在某一区间中排列越靠后的数对以后区间的影响越大，即它在以后区间出现的可能性越大，但未经严格数学证明。,例题6：种树（NOIP模拟试题）,一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号为1.n。每个块大小为一个单位尺寸并最多可种一棵树。每个居民想在门前种些树并指定了三个号码b,e,t。这三个数表示该居民想在b和e之间最少种t棵树。当然b=e,居民必须保证在指定地区不能种多于地区

48、被分割成块数的树，即要求t=e-b+1。允许居民想种树的各自区域可以交叉。出于资金短缺的原因,环保部门请你求出能够满足所有居民的要求,需要种树的最少数量。,样例输入: 9 4 1 4 2 4 6 2 8 9 2 3 5 2 样例输出： 5,分析,方法1：贪心策略 方法2：利用差分约束系统解决 方法3：使用树状数组,3、区间覆盖问题,给n个闭区间ai,bi，选择尽量少的区间覆盖一条指定线段s,t。,本题的突破口仍然是区间包含和排序扫描，不过先要进行一次预处理。每个区间在s,t外的部分都应该预先被切掉，因为它们的存在是毫无意义的。在预处理后，在相互包含的情况下，小区间显然不应该考虑。,把各区间按照

49、a从小到大排序，若a相同，则b从大到小排序（自动处理掉区间包含）。注意：若区间1的起点大于s，则无解（因为其他区间的起点更大，不可能覆盖到s点），否则选择起点在s的最长区间ai,bi后，新的起点应该设置为bi，并且忽略所有区间在bi之前的部分，就像预处理一样。虽然贪心策略比上题复杂，但是仍然只需要一次扫描，如下图，s为当前有效起点（此前部分已被覆盖），则应该选择区间2。,贪心思想：在某个时刻s，找一个满足ai=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：区间（SDOI2005）,现给定n个闭区间ai,bi，1=i=n。这些区间的并可以表示为一些不相交的闭区间的并。你的任务就是在这些表示方式中找出包含最少区间的方案。你的输出应该按照区间的升序排列。这里如果说两个区间a, b和c, d是按照升序排列的，那么我们有ab=c=d。 任务：读入这些区间，计算满足给定条件的不相交闭区间，并把这些区间按照升序输出。,例题8：喷水装置,有一块草坪，长为L，宽为w；在它的中心线上装有n个点状的喷水装置