1、NOIP基礎(chǔ)算法分治與貪心,第五部分,分治策略,一、分治思想,分治法，又叫分治策略，顧名思義，分而治之。 它的基本思想：對于難以直接解決的規(guī)模較大的問題，把它分解成若干個能直接解決的相互獨立的子問題，遞歸求出各子問題的解，再合并子問題的解，得到原問題的解。 通過減少問題的規(guī)模，逐步求解，能夠明顯降低解決問題的復(fù)雜度。,二、分治法的適用條件,能使用分治法解決的問題，它們一般具備以下幾個特征： 該問題可分解成若干相互獨立、規(guī)模較小的相同子問題； 子問題縮小到一定的程度就能輕易得到解； 子問題的解合并后，能得到原問題的解； 分治法在信息學(xué)競賽中應(yīng)用非常廣泛，使用分治策略能生成一些常用的算法和數(shù)據(jù)結(jié)構(gòu)

2、，如快排、最優(yōu)二叉樹、線段樹等；還可以直接使用分治策略，解決一些規(guī)模很大、無法直接下手的問題。,三、分治的三步驟,分解：將要解決的問題分解成若干個規(guī)模較小的同類子問題； 解決：當(dāng)子問題劃分得足夠小時，求解出子問題的解。 合并：將子問題的解逐層合并成原問題的解。,分治算法設(shè)計過程圖,在劃分問題時，可以采用遞歸策略，把一個大問題逐步分解成規(guī)模較小的子問題，直至可以直接求出子問題的解；再將子問題逐層合并，返回到頂層，得到原問題的解。 根據(jù)分治策略的劃分原則，把原問題劃分成多少個子問題才合適呢？各個子問題的規(guī)模應(yīng)該多大才合適呢？ 一般來說，每次劃分成2個子問題，每個子問題的規(guī)模差不多最合適。合并解時要

3、因題而異，有些問題遞歸分解完能直接得到原問題的解，有些問題需逐層合并，得到原問題的解。,四、分治的框架結(jié)構(gòu),procedure Divide() begin if(問題不可分)then/解決 begin 直接求解； 返回問題的解； end else begin 對原問題進行分治；/分解 遞歸對每一個分治的部分進行求解; /解決 歸并整個問題，得出全問題的解; /合并 end end;,五、分治的典型應(yīng)用,1、求最大值和最小值 2、求方程的根 3、二分查找 4、歸并排序 5、快速冪 6、求解線性遞推關(guān)系 7、棋盤覆蓋問題 8、循環(huán)日程表問題 9、尋找最近點對,1、求最大值和最小值,例題1：給n個

4、數(shù)，求它們之中最大值和最小值，要求比較次數(shù)盡量小。,分析：假設(shè)數(shù)據(jù)個數(shù)為n,存放在數(shù)組a1.n中。可以直接進行比較： minn:=a1;maxx:=a1; for i:=2 to n do if aimaxx then maxx:=ai; else if aiminn then minn:=ai; 使用這一算法，比較次數(shù)為2(n-1)。若n=10,則比較18次。,【方法2】分治策略 劃分：把n個數(shù)均分為兩半。即：劃分點為d=(r1+r2)/2，兩個區(qū)間為r1,d和d+1,r2。 遞歸求解：求左半的最小值min1 和最大值max1以及右半最小值min2和最大值max2。 合并：max1與max2

5、比較得到所有數(shù)的最大值為maxx； min1與min2比較得到所有數(shù)的最小值為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這樣的一個一元三次方程。給出該方程中各項的系數(shù)(a,b,c,d均為實數(shù))，并約定該方程存在三個不同實根(根的范圍在-100至100之間)，且根與根之差的絕對值=1。要求由小到大

7、依次在同一行輸出這三個實根(根與根之間留有空格)，并精確到小數(shù)點后4位。 【文件輸入】輸入僅一行，有四個數(shù)，依次為a、b、c、d 【文件輸出】輸出也只有一行，即三個根(從小到大輸出) 【樣例輸入】1 -5 -4 20 【樣例輸入】-2.00 2.00 5.00,分析,如果精確到小數(shù)點后兩位，可用簡單枚舉法：將x從-100.00 到100.00（步長0.01）逐一枚舉，得到20000個 f(x)，取其值與0最接近的三個f(x)，對應(yīng)的x即為答案。而題目已改成精度為小數(shù)點后4位，枚舉算法時間復(fù)雜度將達不到要求。 直接使用求根公式，極為復(fù)雜。加上本題的提示給我們以啟迪：采用二分法逐漸縮小根的范圍，從

8、而得到根的某精度的數(shù)值。,分析,A.當(dāng)已知區(qū)間(a,b)內(nèi)有一個根時； 用二分法求根，若區(qū)間(a,b)內(nèi)有根，則必有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)中,對此區(qū)間重復(fù)該過程。 執(zhí)行完畢,就可以得到精確到0.0001的根。,分析,B、求方程的所有三個實根 所有的根的范圍都在-100至100之間，且根與根之差的絕對值=1。因此可知：在-100,-99、-99,-98、99，100、100，100這201個區(qū)間內(nèi)，每個區(qū)間內(nèi)至多只能有一個根。即：除區(qū)

9、間100，100外，其余區(qū)間a,a+1，只有當(dāng)f(a)=0或f(a)*f(a+1)0時，方程在此區(qū)間內(nèi)才有解。若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、歸并排序,歸并排序的基本思想：歸并排序充分應(yīng)用分治算法的策略，通過二分的思想，將n個數(shù)最終分成n個單獨的有序數(shù)列，每個數(shù)列中僅有一個數(shù)字；再將相鄰的兩列數(shù)據(jù)合并成一個有序數(shù)列；再重復(fù)上面的合并操作，直到合成一個有序數(shù)列。按照分治三步法來說： （1）劃分：把序列分成元素個數(shù)相等的兩半； （2）遞歸求解：把兩半分別排序； （3）合并：把兩個有序表合成一個有序表；,分析,顯然，前兩部分是很容易完成的，關(guān)鍵在于如何把兩個有序表合成一個。每次只需要把兩個有序表中當(dāng)前的最小元素加以比較，刪除較小元素并加入合并后的新表中。,核心參考代碼,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】求逆序?qū)?shù)目,例題3：求“逆序?qū)Α?給定一整數(shù)數(shù)組A=(A1,A2,An), 若iAj,則就為一個逆序?qū)?。例如?shù)組（3，1，4，5，2）的逆序?qū)τ?。問題是，輸入n和A數(shù)組，統(tǒng)計逆序?qū)?shù)目。 數(shù)據(jù)范圍：1=n=30000。,方法1：樸素算法,在看完試題以后，我們不難想到一個非常簡單的算法窮舉算法，即對數(shù)組中任意的兩個元素進行判斷，看它們是不是構(gòu)成“逆序?qū)Α保虼诉@種算法的時間

13、復(fù)雜度為O(N2)。 c:=0; for i:=1 to n -1 do for j:=i+1 to n do if aiaj then c:=c+1; 時間效率不盡如人意. 問題出現(xiàn)在哪里呢？,求逆序?qū)Φ姆椒ǎ?求逆序?qū)τ卸喾N方法， 目前使用比較廣泛且實現(xiàn)比較簡單的主要有三種算法： 1、歸并排序 2、線段樹 3、樹狀數(shù)組,方法2：分治策略,采用二分法求解: 記數(shù)列ast,ed的逆序?qū)?shù)目為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)表示一個數(shù)取自ast,mid,另一

14、個數(shù)取自amid+1,ed所構(gòu)成的逆序?qū)?shù)目。,和歸并排序一樣，劃分和遞歸求解都好辦，關(guān)鍵在于合并：如何求出i在左邊，而j在右邊的逆序?qū)?shù)目呢？統(tǒng)計的常見技巧是“分類”。我們按照j的不同把這些“跨越兩邊”的逆序?qū)M行分類：只要對于右邊的每個j，統(tǒng)計左邊比它大的元素個數(shù)f(j)，則所有f(j)之和便是答案。 幸運的是，歸并排序可以幫助我們“順便”完成f(j)的計算：由于合并操作是從小到大進行排序的，當(dāng)右邊的aj復(fù)制到T中時，左邊還沒有來得及復(fù)制到T的那些數(shù)就是左邊所有比aj大的數(shù)。此時累加器中加上左邊元素個數(shù)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個不同數(shù)a1an，試判斷元素x是否出現(xiàn)在表中。,方法1：順序查找。即一個一個進行尋找，時間復(fù)雜度為O(n)。這個方法并沒有用到“n個數(shù)從小到大排列”這一個關(guān)鍵條件，因而時間效率低下。,方法2：二分查找,只需要比較log2n個元素。假設(shè)需要在aLar中查找元素x。 劃分：檢查某個元素am(Lx，那么元素只可能在aLam-1中 如果amx，那么元素只可能在am+1ar中。 合并：不需要合并。

16、,實現(xiàn)方法1：二分查找的遞歸實現(xiàn),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;,實現(xiàn)方法2：二分查找的非遞歸實現(xiàn),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】二分查找求下界，即第一次出現(xiàn)的位置 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】二分查找求上界，即最后一次出現(xiàn)位置的后一個位置,【變形1】：奇怪的函數(shù),【問題描述】使得xx達到或超過n位數(shù)字的最小正整數(shù)x是多少？ 【文件輸入】輸入一個正整數(shù)n。 【文件輸出】輸出使得xx

18、達到n位數(shù)字的最小正整數(shù)x。,【變形2】：統(tǒng)計,【問題描述】給你一個有n(n=100000)個整數(shù)的序列，接下來有m(m=10000)個詢問，每個詢問為一個整數(shù)，需要你輸出在給出的序列中，此整數(shù)有多少個?,【變形3】：查找等值點,【問題描述】n個不同整數(shù)從小到大排序后放在數(shù)組A1An中，是否存在i，使得Ai=i？若存在，試找到此點。,5、快速冪,【問題】計算an mod k的值 ，其中n=109。,方法1：樸素算法。每次乘以a，時間復(fù)雜度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是偶數(shù)，則考慮x=n div 2 否則考慮x=(n-1) div 2 遞歸求解：計算ax。 合并：如果n是偶數(shù)，則an=(ax)2，否則an=(ax)2*a,方法2：分治算法,根據(jù)這個方法很容易寫出程序： function power(a,n:integer):integer; Begin if n=0 begin power:=1;exit;end else if n mod 2=1 then /n為奇數(shù)的情況 begin x:=power(a,(n-1)div 2); pow

20、er:=(x*x)mod k*a)mod k; end else begin /n為偶數(shù)的情況 x:=power(a,n div 2); power:=x*x mod k; end; End;,方法3：用二進制實現(xiàn)快速冪計算,read(a,b,k);/輸入三個數(shù) t:=b; while t0 do begin inc(len);clen:=t mod 2;t:=t div 2;end;/轉(zhuǎn)為二進制 s:=1; for i:=len downto 1 do /用二分法實現(xiàn)ab mod k begin s:=s*s mod k; if ci=1 then s:=(a mod k)*s)mod k;

21、/是奇數(shù) end; writeln(s);/輸出ab mod k,6、求解線性遞推關(guān)系,【例題】Fibonacci數(shù) 【題目描述】Fibonacci數(shù)列定義為：fi=fi-2+fi-1 (i2)，其中f1=1,f2=1?，F(xiàn)在請你求Fibonacci數(shù)列的第n項。 【文件輸入】輸入文件只有一行為一個整數(shù)n(1=n=231-1)。 【文件輸出】輸出文件只有一行為一個整數(shù)，表示Fibonacci數(shù)列的第n項mod 32768的值。 【樣例輸入】4 【樣例輸出】3 【數(shù)據(jù)范圍】 對于20%的數(shù)據(jù)，1=n=1000 對于40%的數(shù)據(jù)，1=n=10000000 對于100%的數(shù)據(jù)，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;,先復(fù)習(xí)矩陣乘法 兩個2*2矩陣相乘的公式為,可用倍增法在O(logn)時間內(nèi)求出冪(忽略高精度),擴展練習(xí)：,若fi=fi-1+fi-2+fi-3，如何計算求出fn?,7、棋盤覆蓋問題,分析,8、循環(huán)日程表問題,【例題】比賽安排 【問題描述】設(shè)有2n(n=6)個球隊進行單循環(huán)比賽,計劃在2n -1天內(nèi)完成，每個隊每天進行一場比賽。設(shè)計一個比賽的安排，使在2n -1天內(nèi)每個隊都與不同

23、的對手比賽。例如n=2時的比賽安排為： 隊 1 2 3 4 比賽 1-2 3-4 第一天 1-3 2-4 第二天 1-4 2-3 第三天 【文件輸入】一個整數(shù)n。 【文件輸出】輸出比賽安排表。 【樣例輸入】2 【樣例輸出】 1-2 3-4 1-3 2-4 1-4 2-3,分析1：遞歸形式實現(xiàn),由于N個運動員要進行單循環(huán)比賽，且在N-1天內(nèi)要結(jié)束全部比賽，經(jīng)過分析，當(dāng)且僅當(dāng)N為2的整次冪時，問題才有解，當(dāng)然解是不唯一的。這樣可以將運動員分成兩組： 1,2,N/2 和 N/2+1,N/2+2,N。給第一組運動員安排一個比賽日程，得到一個N/2階的方陣A1；同時給第二組的運動員安排一個比賽日程，同樣

24、會得到一個N/2階的一個方陣A2。考慮到比賽的性質(zhì)，設(shè)定第I個運動員在某一天的比賽對手為第K個運動員，則第K個運動員在同一天的比賽對手必然是第I個運動員，即若有AI,J=K，則AK,J=I。因此原問題的解(一個N階方陣)可以由分解后的兩個子問題的解，合并起來。同時每一個子問題又可以按照上述的二分法分解下去，直至每個組中僅有2個運動員時為止。,procedure arrangment(K,N:integer); 從K號運動員起的共N員運動員單循環(huá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 合并子問題的解,構(gòu)造原問題的解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：遞歸形式實現(xiàn),初看此題，感覺無法下手，因為沒有任何直接可用的算法和數(shù)據(jù)結(jié)構(gòu)。 仔細(xì)分析，可以發(fā)現(xiàn)，將問題進行分解，能找出規(guī)律。 當(dāng)n=1時，共有2個球隊參賽，一天就可以比完。 當(dāng)n=2時，共有4個球隊，需比賽3天。從2個球隊的比賽安排表中可以看出，左上角與右下角對稱，左下角與右上角對稱，左下角的值是由左上角值加n得到的。,方法2：遞推實現(xiàn),read(n); m:=1;a1,1:=1;h:=1; for i:=1 to n do m=2*m; /比賽總隊數(shù) while(h=m)do /從一個球隊開始構(gòu)造 begin for i:=1 to h do/構(gòu)造其余三個方陣

27、 for j:=1 to h do begin ai,j+h:=ai,j+h; /構(gòu)造右上角方陣 ai+h,j:=ai,j+h; /構(gòu)造左下角方陣 ai+h,j+h:=ai,j; /構(gòu)造右下角方陣 end; h:=h*2; end;,核心參考代碼：,9、尋找最近點對,【問題描述】給定平面上n (n=60000)個點,找出其中的一對點的距離,使得在這n個點的所有點對中,該距離為所有點對中最小的。,分析,【問題簡述】給定平面上n個點的坐標(biāo)，找出其中歐幾里德距離最近的兩個點。 【方法1】枚舉算法。需要枚舉O(n2)個點對，每個距離的計算時間為O(1)，故總的時間復(fù)雜度為O(n2)。,有沒有更好的算法

28、呢？,【方法2】分治算法,劃分：先按照X坐標(biāo)排序，把所有點劃分成個數(shù)盡量相等的兩部分，分別求最近點對，設(shè)距離分別為dL和dr。,合并：令d=mindL,dr，則跨越兩邊的點對中，只有下面的豎條中的才有可能更近。,需要檢查豎條里的所有點對嗎？,從上往下看, 對于任何一個p, 另一側(cè)可能與它組成更近的點對在一個正方形中, 它最多只有4個點(否則這個方格中會有距離比d小的點對) 最壞情況(同一行的紅藍點幾乎重合), 需要檢查接下來的7個點(紅藍點混在一起),時間復(fù)雜度O(nlogn),總結(jié)歸納,分治是一種解題的策略，它的基本思想是：“如果整個問題比較復(fù)雜，可以將問題分化，各個擊破?！?分治包含“分”

29、和“治”兩層含義，如何分，分后如何“治”成為解決問題的關(guān)鍵所在 不是所有的問題都可以采用分治，只有那些能將問題分成與原問題類似的子問題，并且歸并后符合原問題的性質(zhì)的問題，才能進行分治 分治可進行二分，三分等等，具體怎么分，需看問題的性質(zhì)和分治后的效果。 只有深刻地領(lǐng)會分治的思想，認(rèn)真分析分治后可能產(chǎn)生的預(yù)期效率，才能靈活地運用分治思想解決實際問題。,第六部分,貪心策略,一、貪心策略的基本思想,定義：貪心法是一種解決最優(yōu)問題的策略。它是從問題的初始解出發(fā)，按照當(dāng)前最佳的選擇，把問題歸納為更小的相似的子問題，并使子問題最優(yōu)，再由子問題來推導(dǎo)出全局最優(yōu)解。 使用貪心方法需要注意局部最優(yōu)與全局最優(yōu)的關(guān)

30、系，選擇當(dāng)前狀態(tài)的局部最優(yōu)并不一定能推導(dǎo)出問題的全局最優(yōu)。,【引例】在一個NM的方格陣中，每一格子賦予一個數(shù)值，規(guī)定每次移動時只能向上或向右?，F(xiàn)試找出一條路徑，使其從左下角至右上角所經(jīng)過的數(shù)字之和最大。 我們以23的矩陣為例：,若按貪心策略求解，所得路徑為：1346； 若按動態(tài)規(guī)劃求解，所得路徑為：12106。,二、貪心策略的特點,1.貪心選擇性質(zhì)：算法中每一步選擇都是當(dāng)前看似最佳的選擇，這種選擇依賴于已做出的選擇，但不依賴于未做的選擇。 2.最優(yōu)子結(jié)構(gòu)性質(zhì)：算法中每一次都取得了最優(yōu)解(即局部最優(yōu)解)，要保證最后的結(jié)果最優(yōu)，則必須滿足全局最優(yōu)解包含局部最優(yōu)解。 但并不是所有具有最優(yōu)子結(jié)構(gòu)的問題

31、都可以用貪心策略求解。因為貪心往往是盲目的，需要使用更理性的方法動態(tài)規(guī)劃（例如“0-1背包問題”與“部分背包問題”）,【問題1】部分背包問題,給定一個最大載重量為M的卡車和N種食品，有食鹽，白糖，大米等。已知第i種食品的最多擁有Wi公斤，其商品價值為Vi元/公斤，編程確定一個裝貨方案，使得裝入卡車中的所有物品總價值最大。,【分析】因為每一個物品都可以分割成單位塊，單位塊的利益越大，顯然總收益越大，所以它局部最優(yōu)滿足全局最優(yōu)，可以用貪心法解答。 方法如下：先將單位塊收益按從大到小進行排列，然后用循環(huán)從單位塊收益最大的取起，直到不能取為止便得到了最優(yōu)解。,【問題2】0/1背包問題,給定一個最大載重

32、量為M的卡車和N種動物。已知第i種動物的重量為Wi，其最大價值為Vi，設(shè)定M，Wi，Vi均為整數(shù)，編程確定一個裝貨方案，使得裝入卡車中的所有動物總價值最大。,【分析】按貪心法：每次選價格最大的裝載。很明顯有反例：設(shè)N=3,卡車最大載重量是100,三種動物A、B、C的重量分別是40,50,70,其對應(yīng)的總價值分別是80、100、150。,三、貪心策略與其他算法的區(qū)別,1.貪心與遞推：與遞推不同的是，貪心法中推進的每一步不是依據(jù)某一固定的遞推式，而是當(dāng)前看似最佳的貪心決策，不斷的將問題歸納為更加小的相似的子問題。所以歸納、分析、選擇正確合適的貪心策略，是正確解決貪心問題的關(guān)鍵。 2.貪心與動態(tài)規(guī)劃

33、：與動態(tài)規(guī)劃不同的是，貪心是鼠目寸光；動態(tài)規(guī)劃是統(tǒng)攬全局。,四、貪心策略的證明,貪心策略能否適用，關(guān)鍵看在貪心的策略下，局部的最優(yōu)解能否得到全局最優(yōu)解。要看是否得到最優(yōu)解，就要看貪心選擇特征的證明了。常用的證明法有反證法和構(gòu)造法。 1.反證法：顧名思義，對于當(dāng)前的貪心策略，否定當(dāng)前的選擇，看看是否能得到最優(yōu)解，如果不能得到，說明當(dāng)前貪心策略是正確的；否則，當(dāng)前策略不正確，不可用。 2.構(gòu)造法：對于題目給出的問題，用貪心策略時，把問題構(gòu)造成已知的算法或數(shù)據(jù)結(jié)構(gòu)，以此證明貪心策略是正確的。,五、幾個簡單的貪心例子,貪心策略,例題1：排隊問題,【問題描述】在一個食堂，有n個人排隊買飯，每個人買飯需要

34、的時間為Ti，請你找出一種排列次序，使每個人買飯的時間總和最小。 【輸入文件】輸入文件共兩行，第一行為n；第二行分別表示第1個人到第n個人每人買飯的時間T1,T2,Tn。 【輸出文件】輸出文件僅一行為買飯的時間總和。 【樣例輸入】 6 5 3 7 1 9 10 【樣例輸出】 90,【思路點撥】假設(shè)取水的人按照1.n的順序排列的，那么問題就轉(zhuǎn)化為求以下公式的最小值： Total=T1+(T1+T2)+(T1+T2+T3)+.+(T1+T2+.+Tn)，對公式換個寫法： Total=nT1+(n-1)T2+(n-2)T3.+2Tn-1+Tn 現(xiàn)在你是否發(fā)現(xiàn)一點什么呢？ 如果讓T1=Total，兩者

35、相比較，可知有序的序列能得到最優(yōu)的方案。 對于其他位置的改變可以采用同樣的方法證明。用反證法證明時，關(guān)鍵是證明反例不成立，由此推出原方案是最優(yōu)的。,問題推廣1：排隊打水問題,【問題描述】有n個人在一個水龍頭前排隊接水，假如每個人接水的時間為Ti，請編程找出這n個人排隊的一種順序，使得這n個人的平均等待時間最小。 【輸入文件】輸入文件共兩行，第一行為n；第二行分別表示第1個人到第n個人每人的接水時間T1,T2,Tn。 【輸出文件】輸出文件僅一行為最小的平均等待時間。 【樣例輸入】 6 5 3 7 1 9 10 【樣例輸出】 15,【思路點撥】首先需要理解平均等待時間的概念。平均等待時間就是每個人

36、的等待時間之和再除以n，因為n是個常數(shù)，所有等待時間之和最小也就等同于平均等待時間最小。 這樣就轉(zhuǎn)化為前面的問題了,問題推廣2：排隊打水問題,【問題描述】有n個人排隊到r個水龍頭去打水，他們裝滿水桶的時間T1、T2,Tn為整數(shù)且各不相等，應(yīng)如何安排他們的打水順序才能使他們總共花費的時間最少？ 【文件輸入】輸入文件共計兩行，第一行n，r(n=500,r=75)，第二行為n個人打水所用的時間Ti (Ti=100)； 【文件輸出】輸出文件只有一行為n個人打完水的最少總共花費時間。 【樣例輸入】 3 2 1 2 3 4 【樣例輸出】13,例題2：打包,某工廠生產(chǎn)出的產(chǎn)品都要被打包放入正四棱柱的盒子內(nèi)，

37、所有盒子的高度為h，但地面尺寸不同，可以為 1x1、2x2、3x3、4x4、5x5、6x6。如下圖所示。,這些盒子將被放入高度為h，地面尺寸為6x6的箱子中。為了降低運送成本，工廠希望盡量減少箱子的數(shù)量。如果有一個好算法，能使箱子的數(shù)量降到最低，這將給工廠節(jié)省不少的資金。請你編寫一個程序。,分析,分析,例題3:均分紙牌（NOIP2002）,有N堆紙牌，編號分別為 1,2,N。每堆上有若干張，但紙牌總數(shù)必為N的倍數(shù)?？梢栽谌我欢焉先∪粲趶埣埮?，然后移動。 移牌規(guī)則為：在編號為1堆上取的紙牌，只能移到編號為2的堆上；在編號為N的堆上取的紙牌，只能移到編號為N-1的堆上；其他堆上取的紙牌，可以移到相

38、鄰左邊或右邊的堆上。 現(xiàn)在要求找出一種移動方法，用最少的移動次數(shù)使每堆上紙牌數(shù)都一樣多。 例如 N=4，4 堆紙牌數(shù)分別為：98176 移動3次可達到目的：從取4張牌放到(9 8 13 10)-從取3張牌放到(9 11 10 10)-從取1張牌放到(10 10 10 10）。,【文件輸入】第一行為一個整數(shù)N(N堆紙牌,1=N=100)，第二行為n個用空格分開的整數(shù)，依次為A1 A2 An(N堆紙牌，每堆紙牌初始數(shù)，l=Ai=10000)。 【文件輸出】所有堆均達到相等時的最少移動次數(shù)。 【樣例輸入】 4 9 8 17 6 【樣例輸出】3,分析：,【試題分析】我們要使移動次數(shù)最少，就是要把浪費降

39、至零。通過對具體情況的分析，可以看出在某相鄰的兩堆之間移動兩次或兩次以上，是一種浪費，因為我們可以把它們合并為一次或零次。 【思路點撥】如果你想到把每堆牌的張數(shù)減去平均張數(shù)，題目就變成移動正數(shù)，加到負(fù)數(shù)中，最終使大家都變成0，那就意味著成功了一半！ 從第i堆移動-m張牌到第i+1堆，等價于從第i+1堆移動m張牌到第i堆，步數(shù)是一樣的。 注意最左邊的0和最右邊的0不能算在內(nèi)，如0,0,1,-3,4,0,-1,0,0,擴展1：（NOIP模擬試題）,若題目中的紙牌排成一個環(huán)狀，應(yīng)如何處理呢？ 其中n=1000。,擴展2：（2011重慶省選）,有n個小朋友坐成一圈，每人有ai個糖果。每人只能給左右兩人

40、傳遞糖果。每人每次傳遞一個糖果代價為1。求使所有人獲得均等糖果的最小代價。 【數(shù)據(jù)規(guī)?！?對于30%的數(shù)據(jù)n=1000； 對于100%的數(shù)據(jù)n=1000000,例題4:射擊比賽（CEOI1997）,我們假設(shè)射擊的目標(biāo)是一個由R*C(2RC 1000)個小方格組成的矩形網(wǎng)格。網(wǎng)格中每一列恰有2個白色的小方格和R-2個黑色的小方格。定義網(wǎng)格的行從頂至底編號為1R，列從左至右編號為1C。 射擊者可射擊C次。在連續(xù)的C次射擊中，若每列恰好有一個白色的方格被射中，且不存在無白色方格被射中的行，這樣的射擊才是正確的。問題是，如果存在正確的射擊方法，則要求找到它。,例如考慮如下目標(biāo)：由上圖可以看出，在每列中

41、依次射中的行坐標(biāo)為2,3,1,4?，F(xiàn)在要求你編程計算出是否有正確的射擊方法。,根據(jù)題設(shè)條件，射擊的選擇有2C種，符合要求的卻很少。要解決問題，還需從正確的射擊方法的特征入手。,【方法1】網(wǎng)絡(luò)流算法,我們將表示列的點編號為1到C，表示行的點編號為C+1到C+R，如果一個白色方格處在第i行第j列，那么從點j向點C+i連一條弧，弧的容量為1。再增設(shè)一個源點S，從點S往點1到C間各連一條弧，弧的容量為1，又設(shè)一個匯點T，從點C+1到點C+R向匯點T連一條弧，弧的容量為1，那么從源點S到匯點T求最大流，求出的最大流量即為最多可以射擊到的行數(shù)。各條流的路線則描述了具體的射擊方案。 顯然，如果用網(wǎng)絡(luò)流求出的

42、最大流量比R小，則問題無解，否則我們可以根據(jù)網(wǎng)絡(luò)流的結(jié)果求出該二分圖的具體匹配方案。,紅色的連線流量為1 藍色的連線流量為0 選擇的射擊格即為： (1,3), (2,1), (3,2), (4,4),網(wǎng)絡(luò)流算法經(jīng)過優(yōu)化，時間復(fù)雜度可以達到O(C*(n+4C+4R) 上述網(wǎng)絡(luò)流算法雖然可以通過全部數(shù)據(jù)，但編程復(fù)雜度很高，而且極易出錯，一不小心就會因為一個小錯誤影響整個程序。,【方法二】貪心方法 1、統(tǒng)計所有行包含的白格數(shù) 2、從還沒有射擊格的行中選出一個白格數(shù)最少的 3、檢查所選的行 （1）若所選行的白格數(shù)為0，則輸出無解； （2）否則從所選行的白格中任選一個作為射擊格，并將與該格同列的另一個白

43、格所處行的白格數(shù)減1 4、返回到第2步，直到所有的行都有射擊格。 5、若還有列沒有選射擊格，則在該列任選一白格作為射擊格即可,上面的貪心方法非常高效： 時間復(fù)雜度為O(RC)，如果在程序中使用堆優(yōu)化，時間復(fù)雜度將降為O(Rlog2C)?？臻g復(fù)雜度是線性的，而且非常容易實現(xiàn)。 現(xiàn)在關(guān)鍵的問題就是如何證明它的正確性？,證明：,用hi表示第i行的白格數(shù)。如果最開始的時候： minhi=0：第i行已經(jīng)沒有辦法找到可作為射擊格的白格，那么問題只能無解。 minhi=1：那么第i行的這一個白格必須要作為射擊格，否則將因第i行沒有射擊格而造成問題無解。 minhi2：那么在這一行任選一個白格,頂多只會造成剩

44、余行中有一行h值為1,再處理那一行，最多也只會再造成剩余行中有一行h值為1，如此往復(fù),將保持h值為1的行數(shù)不超過1行，最后最壞的情況也是造成最后一行的h值為1,繼續(xù)下去所有行就都已選取了射擊格了。 因此，如果原問題有解，該貪心方法一定能找到一種正確的方案。由此可以證明，此貪心方法是正確的。確定貪心標(biāo)準(zhǔn)。,六、貪心的經(jīng)典應(yīng)用,（一）、三個區(qū)間上的問題 1、選擇不相交區(qū)間問題 2、區(qū)間選點問題 3、區(qū)間覆蓋問題 （二）、兩個調(diào)度問題 1、流水作業(yè)調(diào)度問題 2、帶限期和罰款的單位時間任務(wù)調(diào)度 （三）Huffman編碼 （四）最優(yōu)合并問題,1、選擇不相交區(qū)間問題,給定n個開區(qū)間(ai, bi)，選擇盡

45、量多個區(qū)間，使得這些區(qū)間兩兩沒有公共點。,【算法實現(xiàn)】首先按照b1=b2=bn的順序排序，依次考慮各個活動，如果沒有和已經(jīng)選擇的活動沖突，就選；否則就不選。,貪心策略：取滿足條件的第一個區(qū)間；,【正確性】：如果不選b1，假設(shè)第一個選擇的是bi，則如果bi和b1不交叉則多選一個b1更劃算；如果交叉則把bi換成b1不影響后續(xù)選擇。,（一）、三個區(qū)間上的問題,【樣例輸入】 6 3 4 6 7 1 3 2 5 5 6 4 7 【樣例輸出】4,按照bi從小到大排序后的結(jié)果為： 1 3 3 4 2 5 5 6 4 7 6 7 選擇的區(qū)間為： 1 3 3 4 5 6 6 7,例題5：活動安排,設(shè)有n個活動，

46、每個活動都要求使用同一資源，如演講會場等，而在同一時間內(nèi)只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結(jié)束時間fi，且si=sj或fj=si時，活動i與活動j相容。選擇出由互相兼容的活動組成的最大集合。,2、區(qū)間選點問題,給定n個閉區(qū)間ai, bi，在數(shù)軸上選盡量少的點，使得每個區(qū)間內(nèi)都至少有兩個不同點（不同區(qū)間內(nèi)含的點可以是同一個）。,【算法】：先按照所有區(qū)間的結(jié)束位置從小到大排序。從區(qū)間1到區(qū)間n進行循環(huán)，對于當(dāng)前區(qū)間，若已選中的數(shù)不能覆蓋它，則從區(qū)間末尾向前掃描，若當(dāng)前數(shù)未選中出現(xiàn)，則將該數(shù)標(biāo)記為已選中，直至使選中的數(shù)能滿足該區(qū)間要求為止。,【樣例輸入】

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,上述算法的指導(dǎo)思想是在某一區(qū)間中排列越靠后的數(shù)對以后區(qū)間的影響越大，即它在以后區(qū)間出現(xiàn)的可能性越大，但未經(jīng)嚴(yán)格數(shù)學(xué)證明。,例題6：種樹（NOIP模擬試題）,一條街的一邊有幾座房子。因為環(huán)保原因居民想要在路邊種些樹。路邊的地區(qū)被分割成塊，并被編號為1.n。每個塊大小為一個單位尺寸并最多可種一棵樹。每個居民想在門前種些樹并指定了三個號碼b,e,t。這三個數(shù)表示該居民想在b和e之間最少種t棵樹。當(dāng)然b=e,居民必須保證在指定地區(qū)不能種多于地區(qū)

48、被分割成塊數(shù)的樹，即要求t=e-b+1。允許居民想種樹的各自區(qū)域可以交叉。出于資金短缺的原因,環(huán)保部門請你求出能夠滿足所有居民的要求,需要種樹的最少數(shù)量。,樣例輸入: 9 4 1 4 2 4 6 2 8 9 2 3 5 2 樣例輸出： 5,分析,方法1：貪心策略 方法2：利用差分約束系統(tǒng)解決 方法3：使用樹狀數(shù)組,3、區(qū)間覆蓋問題,給n個閉區(qū)間ai,bi，選擇盡量少的區(qū)間覆蓋一條指定線段s,t。,本題的突破口仍然是區(qū)間包含和排序掃描，不過先要進行一次預(yù)處理。每個區(qū)間在s,t外的部分都應(yīng)該預(yù)先被切掉，因為它們的存在是毫無意義的。在預(yù)處理后，在相互包含的情況下，小區(qū)間顯然不應(yīng)該考慮。,把各區(qū)間按照

49、a從小到大排序，若a相同，則b從大到小排序（自動處理掉區(qū)間包含）。注意：若區(qū)間1的起點大于s，則無解（因為其他區(qū)間的起點更大，不可能覆蓋到s點），否則選擇起點在s的最長區(qū)間ai,bi后，新的起點應(yīng)該設(shè)置為bi，并且忽略所有區(qū)間在bi之前的部分，就像預(yù)處理一樣。雖然貪心策略比上題復(fù)雜，但是仍然只需要一次掃描，如下圖，s為當(dāng)前有效起點（此前部分已被覆蓋），則應(yīng)該選擇區(qū)間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從小到大排序后的結(jié)果為： 1 4 1 3 2 5 3 10 3 8 4 6 7 10,例題7：區(qū)間（SDOI2005）,現(xiàn)給定n個閉區(qū)間ai,bi，1=i=n。這些區(qū)間的并可以表示為一些不相交的閉區(qū)間的并。你的任務(wù)就是在這些表示方式中找出包含最少區(qū)間的方案。你的輸出應(yīng)該按照區(qū)間的升序排列。這里如果說兩個區(qū)間a, b和c, d是按照升序排列的，那么我們有ab=c=d。 任務(wù)：讀入這些區(qū)間，計算滿足給定條件的不相交閉區(qū)間，并把這些區(qū)間按照升序輸出。,例題8：噴水裝置,有一塊草坪，長為L，寬為w；在它的中心線上裝有n個點狀的噴水裝置