NOIP基礎(chǔ)算法——貪心和分治pascal

1、NOIP基礎(chǔ)算法分治與貪心,巴蜀中學(xué) 黃新軍,:8080/bsoi,第四部分 分治策略,一、分治思想,分治(divide-and-conquer)就是“分而治之”的意思，其實質(zhì)就是將原問題分成n個規(guī)模較小而結(jié)構(gòu)與原問題相似的子問題；然后遞歸地解這些子問題，最后合并其結(jié)果就得到原問題的解。,二、分治法的適用條件,能使用分治法解決的問題，它們一般具備以下幾個特征： 該問題可以分解成若干相互獨(dú)立、規(guī)模較小的相同子問題； 子問題縮小到一定的程度就能輕易得到解； 子問題的解合并后，能得到原問題的解； 分治法在信息學(xué)競賽中應(yīng)用非常廣泛，使用分治策略能生成一些常用的算法和數(shù)據(jù)結(jié)構(gòu)，如快排、最優(yōu)二叉樹、線段樹

2、等；還可以直接使用分治策略，解決一些規(guī)模很大、無法直接下手的問題。,三、分治的三步驟,分解：將要解決的問題分解成若干個規(guī)模較小的同類子問題； 解決：當(dāng)子問題劃分得足夠小時，求解出子問題的解。 合并：將子問題的解逐層合并成原問題的解。,分治算法設(shè)計過程圖,由分治法所得到的子問題與原問題具有相同的類型。如果得到的子問題相對來說還太大，則可反復(fù)使用分治策略將這些子問題分成更小的同類型子問題，直至產(chǎn)生出不用進(jìn)一步細(xì)分就可求解的子問題。分治求解可用一個遞歸過程來表示。 要使分治算法效率高，關(guān)鍵在于如何分割？一般地，出于一種平衡原則，總是把大問題分成K個規(guī)模盡可能相等的子問題，但也有例外，如求表的最大最小

3、元問題的算法，當(dāng)n6時，等分定量成兩個規(guī)模為3的子表L1和L2不是最佳分割。一般來講，都是2分為主。,四、分治的框架結(jié)構(gòu),procedure DIVIDE() begin if(問題不可分)then/解決 begin 直接求解； 返回問題的解； end else begin 對原問題進(jìn)行分治；/分解 遞歸對每一個分治的部分求解; 歸并整個問題，得出全問題的解;/合并 end end;,五、分治的典型應(yīng)用,1、求最大值和最小值 2、非線性方程求根 3、二分查找 4、歸并排序 5、快速冪 6、求解線性遞推關(guān)系 7、棋盤覆蓋問題 8、循環(huán)日程表問題 9、尋找最近點對,1、求最大值和最小值,例題1：給

4、n個實數(shù)，求它們之中最大值和最小值，要求比較次數(shù)盡量小。,分析：假設(shè)數(shù)據(jù)個數(shù)為n,存放在數(shù)組a1.n中?？梢灾苯舆M(jì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個正整數(shù)的序列劃分成m個連續(xù)的子序列(每個正整數(shù)恰好屬于一個序列)。設(shè)第i個序列的各數(shù)之和為S(i)，你的任務(wù)是讓所有的S(i)的最大值盡量小。例如序列1 2 3 2 5 4劃分成3個序列的最優(yōu)方案為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、之間留有空格)，并精確到小數(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ù)雜度將達(dá)不到要求。 直接使用求根公式，極為復(fù)雜。加上本題的提示給我們以啟迪：采用二分法逐漸縮小根的范圍，從而得到根的某精度的數(shù)值,分析,A.

7、當(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并退出過程； (2).若f(a)*f(a+b)/2)0,則必然有f(a+b)/2)*f(b)=1。因此可知：在-100,-99、-99,-98、99，100、100，100這201個區(qū)間內(nèi)，每個區(qū)間內(nèi)至多只能有一個根。即：除區(qū)間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中所述的二分法迅速出找出解。如此可求出方程的所

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、歸并排序,歸并排序的基本思想：歸并排序充分應(yīng)用分治算法的策略，通過二分的思想，將n個數(shù)最終分成n個單獨(dú)的有序數(shù)列，每個數(shù)列中僅有一個數(shù)字；再將相鄰的兩列數(shù)據(jù)合并成一個有序數(shù)列；再重復(fù)上面的合并操作，直到合成一個

9、有序數(shù)列。按照分治三步法來說， 歸并過程為： （1）劃分：把序列分成元素個數(shù)相等的兩半； （2）遞歸求解：把兩半分別排序； （3）合并：把兩個有序表合成一個有序表；,分析,顯然，前兩部分是很容易完成的，關(guān)鍵在于如何把兩個有序表合成一個。每次只需要把兩個序列中當(dāng)前的最小元素加以比較，刪除較小元素并加入合并后的新表。,核心參考代碼,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】逆序?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ù)范圍：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個不同數(shù)a1an，試判斷元素x是否出現(xiàn)在表中。,方法1：順序查找。方法是一個個尋找，時間復(fù)雜度

12、為O(n)。這個方法并沒有用到“n個數(shù)從小到大排列”這一個關(guān)鍵條件，因而時間效率低下。,方法2：二分查找,只需要比較log2n個元素。假設(shè)需要在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：二分查找的非遞歸實現(xiàn)：,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;,【擴(kuò)展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; 【擴(kuò)展2】二分查找求上界，即最后一次出現(xiàn)位置的后一個位置,【思考題目】給出n個整數(shù)和m個詢問，每次一個數(shù)字c,問整數(shù)c的

14、個數(shù)。,【思路點撥】 先把所有的數(shù)據(jù)從小到大排序； 二分查找求下界，即第一次出現(xiàn)的位置low； 二分查找求上界，即最后一次出現(xiàn)位置的后一個位置high； 答案區(qū)間為：ans=high-low,【變形1】查找等值點,【問題描述】n個不同整數(shù)從小到大排序后放在數(shù)組A1An中，是否存在i，使得Ai=i？若存在，試找到此點。,5、快速冪,【問題描述】計算an %k ，n2)，其中f1=1,f2=1。現(xiàn)在請你求Fibonacci數(shù)列的第n項。 【文件輸入】輸入文件只有一行為一個整數(shù)n(1=n=231-1)。 【文件輸出】輸出文件只有一行為一個整數(shù)，表示Fibonacci數(shù)列的第n項mod 32768的值

15、。 【樣例輸入】4 【樣例輸出】3 【數(shù)據(jù)范圍】 對于20%的數(shù)據(jù)，1=n=1000 對于40%的數(shù)據(jù)，1=n=10000000 對于100%的數(shù)據(jù)，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;,先復(fù)習(xí)矩陣乘法 兩個2*2矩陣相乘的公式為, 可用倍增法在O(logn)時間內(nèi)求出冪(忽略高精度),一般情形,7、棋盤覆蓋問題,分析,8、循環(huán)日程表問題,【例題】比賽安排 【問題描述】設(shè)有2n(n=6)個球隊進(jìn)行單循環(huán)

16、比賽,計劃在2n -1天內(nèi)完成，每個隊每天進(jìn)行一場比賽。設(shè)計一個比賽的安排，使在2n -1天內(nèi)每個隊都與不同的對手比賽。例如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,初看此題，感覺無法下手，因為沒有任何直接可用的算法和數(shù)據(jù)結(jié)構(gòu)。 仔細(xì)分析，可以發(fā)現(xiàn)，將問題進(jìn)行分解，能找出規(guī)律。 當(dāng)n=1時，共有2個球隊參賽，一天就可以比完。 當(dāng)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; /比賽總隊數(shù) while(h=m)do /從一個球隊開始構(gòu)造 begin for i:=1 to h do 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個點,找出其中的一對點

18、的距離,使得在這n個點的所有點對中,該距離為所有點對中最小的。（n=60000）,分析,【問題簡述】給定平面上n個點的坐標(biāo)，找出其中歐幾里德距離最近的兩個點。 【方法1】枚舉算法。需要枚舉O(n2)個點對，每個距離的計算時間為O(1)，故總的時間復(fù)雜度為O(n2)。,有沒有更好的算法呢？,【方法2】分治算法,先按照X坐標(biāo)排序，把所有點劃分成個數(shù)盡量相等的兩部分，分別求最近點對，設(shè)距離分別為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中的點。設(shè)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）。,分析：,【試題分析】我們要使移動次數(shù)最少，就是要把浪費(fèi)降至零。通過對具體情況的分析，可以看出在某相鄰的兩堆之間移動兩次或兩次以上，是一種浪費(fèi)，因為我們可以把它們合并為一次或零次。 【思路點撥】如果你想到把每堆牌的張數(shù)減

20、去平均張數(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,擴(kuò)展1：,若題目中的紙牌排成一個環(huán)狀，應(yīng)如何處理呢？ 其中n=1000。,擴(kuò)展2：,有n個小朋友坐成一圈，每人有ai個糖果。每人只能給左右兩人傳遞糖果。每人每次傳遞一個糖果代價為1。求使所有人獲得均等糖果的最小代價。 【數(shù)據(jù)規(guī)?！?對于30%的數(shù)據(jù)n=1000； 對于100%的數(shù)據(jù)n=1000000,貪心的經(jīng)典應(yīng)用,（一）、三個區(qū)間上的問題 1、

21、選擇不相交區(qū)間問題 2、區(qū)間選點問題 3、區(qū)間覆蓋問題 （二）、兩個調(diào)度問題 1、流水作業(yè)調(diào)度問題 2、帶限期和罰款的單位時間任務(wù)調(diào)度 （三）Huffman編碼 （四）最優(yōu)合并問題,1、選擇不相交區(qū)間問題,給定n個開區(qū)間(ai, bi)，選擇盡量多個區(qū)間，使得這些區(qū)間兩兩沒有公共點。,【算法實現(xiàn)】首先按照b1=b2=si時，活動i與活動j相容。選擇出由互相兼容的活動組成的最大集合。,2、區(qū)間選點問題,給定n個閉區(qū)間ai, bi，在數(shù)軸上選盡量少的點，使得每個區(qū)間內(nèi)都至少有一個點（不同區(qū)間內(nèi)含的點可以是同一個）。,【算法】：首先按照b1=b2=bn排序。每次標(biāo)記當(dāng)前區(qū)間的右端點X，并右移當(dāng)前區(qū)間

22、指針，直到當(dāng)前區(qū)間不包含X，再重復(fù)上述操作。,貪心策略：取最后一個。,例題6：種樹（NOIP模擬試題）,一條街的一邊有幾座房子。因為環(huán)保原因居民想要在路邊種些樹。路邊的地區(qū)被分割成塊，并被編號為1.n。每個塊大小為一個單位尺寸并最多可種一棵樹。每個居民想在門前種些樹并指定了三個號碼b,e,t。這三個數(shù)表示該居民想在b和e之間最少種t棵樹。當(dāng)然，b=e,居民必須保證在指定地區(qū)不能種多于地區(qū)被分割成塊數(shù)的樹，即要求t=s的bi的最大值即可。,例題7：區(qū)間（SDOI2005）,現(xiàn)給定n個閉區(qū)間ai,bi，1=i=n。這些區(qū)間的并可以表示為一些不相交的閉區(qū)間的并。你的任務(wù)就是在這些表示方式中找出包含最

23、少區(qū)間的方案。你的輸出應(yīng)該按照區(qū)間的升序排列。這里如果說兩個區(qū)間a, b和c, d是按照升序排列的，那么我們有ab=c=d。 任務(wù)：讀入這些區(qū)間，計算滿足給定條件的不相交閉區(qū)間，并把這些區(qū)間按照升序輸出。,練習(xí)試題：噴水裝置,有一塊草坪，長為L，寬為w；在它的中心線上裝有n個點狀的噴水裝置，效果是讓以它為中心半徑為ri的圓被潤濕，選擇盡量少的噴水裝置把整個草坪全部潤濕。,1、流水作業(yè)調(diào)度問題,分析,2、帶限期和罰款的單位時間任務(wù)調(diào)度,貪心方法的推廣,貪心與其它算法結(jié)合 搜索的最優(yōu)化剪枝（ 生日蛋糕） 優(yōu)化動態(tài)規(guī)劃（ Peter的快餐店） 貪心方法與解題策略 最優(yōu)方法不一定是最好方法 想不到最優(yōu)解法就用較優(yōu)解法,貪心與其它算法結(jié)合,例題11：Peter的快餐店（貪心與動態(tài)規(guī)劃） Peter最近在R市新開了一家快餐店。 該快餐店準(zhǔn)備推出一種套餐，每套由A個漢堡、B個薯條和C個飲料組成。為了提高產(chǎn)量，Peter引進(jìn)了N