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

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

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

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

4、n個(gè)實(shí)數(shù)，求它們之中最大值和最小值，要求比較次數(shù)盡量小。,分析：假設(shè)數(shù)據(jù)個(gè)數(shù)為n,存放在數(shù)組a1.n中。可以直接進(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,【思考試題】最大值最小化,【問(wèn)題描述】把一個(gè)包含n個(gè)正整數(shù)的序列劃分成m個(gè)連續(xù)的子序列(每個(gè)正整數(shù)恰好屬于一個(gè)序列)。設(shè)第i個(gè)序列的各數(shù)之和為S(i)，你的任務(wù)是讓所有的S(i)的最大值盡量小。例如序列1 2 3 2 5 4劃分成3個(gè)序列的最優(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。要求由小到大依次在同一行輸出這三個(gè)實(shí)根(根與根

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

7、當(dāng)已知區(qū)間(a,b)內(nèi)有一個(gè)根時(shí)； 用二分法求根，若區(qū)間(a,b)內(nèi)有根，則必有f(a)*f(b)b或f(a+b)/2)=0，則可確定根為(a+b)/2并退出過(guò)程； (2).若f(a)*f(a+b)/2)0,則必然有f(a+b)/2)*f(b)=1。因此可知：在-100,-99、-99,-98、99，100、100，100這201個(gè)區(qū)間內(nèi)，每個(gè)區(qū)間內(nèi)至多只能有一個(gè)根。即：除區(qū)間100，100外，其余區(qū)間a,a+1，只有當(dāng)f(a)=0或f(a)f(a+1)0時(shí)，方程在此區(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)用分治算法的策略，通過(guò)二分的思想，將n個(gè)數(shù)最終分成n個(gè)單獨(dú)的有序數(shù)列，每個(gè)數(shù)列中僅有一個(gè)數(shù)字；再將相鄰的兩列數(shù)據(jù)合并成一個(gè)有序數(shù)列；再重復(fù)上面的合并操作，直到合成一個(gè)

9、有序數(shù)列。按照分治三步法來(lái)說(shuō)， 歸并過(guò)程為： （1）劃分：把序列分成元素個(gè)數(shù)相等的兩半； （2）遞歸求解：把兩半分別排序； （3）合并：把兩個(gè)有序表合成一個(gè)有序表；,分析,顯然，前兩部分是很容易完成的，關(guān)鍵在于如何把兩個(gè)有序表合成一個(gè)。每次只需要把兩個(gè)序列中當(dāng)前的最小元素加以比較，刪除較小元素并加入合并后的新表。,核心參考代碼,tempmaxn; /輔助空間 procedure MergeSort(left,right:integer)/歸并排序 begin if left=right then exit; /只有一個(gè)元素 mid:=(left+right)div 2; /找中間位 Merge

10、Sort(left,mid); /對(duì)左邊歸并 MergeSort(mid+1,right); /對(duì)右邊歸并 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,則就為一個(gè)逆序?qū)?。例如?shù)組（3，1，4，5，2）的逆序?qū)τ?。問(wèn)題是，輸入n和A數(shù)組，統(tǒng)計(jì)逆序?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、二分查找,【問(wèn)題描述】給出從小到大排列的n個(gè)不同數(shù)a1an，試判斷元素x是否出現(xiàn)在表中。,方法1：順序查找。方法是一個(gè)個(gè)尋找，時(shí)間復(fù)雜度

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

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

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

16、比賽,計(jì)劃在2n -1天內(nèi)完成，每個(gè)隊(duì)每天進(jìn)行一場(chǎng)比賽。設(shè)計(jì)一個(gè)比賽的安排，使在2n -1天內(nèi)每個(gè)隊(duì)都與不同的對(duì)手比賽。例如n=2時(shí)的比賽安排為： 隊(duì) 1 2 3 4 比賽 1-2 3-4 第一天 1-3 2-4 第二天 1-4 2-3 第三天 【文件輸入】一個(gè)整數(shù)n。 【文件輸出】輸出比賽安排表。 【樣例輸入】2 【樣例輸出】 1-2 3-4 1-3 2-4 1-4 2-3,初看此題，感覺(jué)無(wú)法下手，因?yàn)闆](méi)有任何直接可用的算法和數(shù)據(jù)結(jié)構(gòu)。 仔細(xì)分析，可以發(fā)現(xiàn)，將問(wèn)題進(jìn)行分解，能找出規(guī)律。 當(dāng)n=1時(shí)，共有2個(gè)球隊(duì)參賽，一天就可以比完。 當(dāng)n=2時(shí)，共有4個(gè)球隊(duì)，需比賽3天。從2個(gè)球隊(duì)的比賽安排

17、表中可以看出，左上角與右下角對(duì)稱(chēng)，左下角與右上角對(duì)稱(chēng)，左下角的值是由左上角值加n得到的。,read(n); m:=1;a1,1:=1;h:=1; for i:=1 to n do m=2*m; /比賽總隊(duì)數(shù) while(h=m)do /從一個(gè)球隊(duì)開(kāi)始構(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、尋找最近點(diǎn)對(duì),給定平面上n個(gè)點(diǎn),找出其中的一對(duì)點(diǎn)

18、的距離,使得在這n個(gè)點(diǎn)的所有點(diǎn)對(duì)中,該距離為所有點(diǎn)對(duì)中最小的。（n=60000）,分析,【問(wèn)題簡(jiǎn)述】給定平面上n個(gè)點(diǎn)的坐標(biāo)，找出其中歐幾里德距離最近的兩個(gè)點(diǎn)。 【方法1】枚舉算法。需要枚舉O(n2)個(gè)點(diǎn)對(duì)，每個(gè)距離的計(jì)算時(shí)間為O(1)，故總的時(shí)間復(fù)雜度為O(n2)。,有沒(méi)有更好的算法呢？,【方法2】分治算法,先按照X坐標(biāo)排序，把所有點(diǎn)劃分成個(gè)數(shù)盡量相等的兩部分，分別求最近點(diǎn)對(duì)，設(shè)距離分別為dL和dr。,合并：令d=mindL,dr，則跨越兩邊的點(diǎn)對(duì)中，只有下面的豎條中的才有可能更近。,需要檢查豎條里的所有點(diǎn)對(duì)嗎？,由d的意義可知，P2中任何2個(gè)S中的點(diǎn)的距離都不小于d。由此而來(lái)可以推出矩形R中

19、最多只有6個(gè)d/2*2/3*d的矩形(如下圖所示)。,（反證法）若矩形R中有多于6個(gè)S中的點(diǎn)，則由鴿籠原理易知至少有一個(gè)d/2*2/3*d的小矩形中有2個(gè)以上S中的點(diǎn)。設(shè)U，V是這樣2個(gè)點(diǎn)，它們位于同一小矩形中，則： (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）。,分析：,【試題分析】我們要使移動(dòng)次數(shù)最少，就是要把浪費(fèi)降至零。通過(guò)對(duì)具體情況的分析，可以看出在某相鄰的兩堆之間移動(dòng)兩次或兩次以上，是一種浪費(fèi)，因?yàn)槲覀兛梢园阉鼈兒喜橐淮位蛄愦巍?【思路點(diǎn)撥】如果你想到把每堆牌的張數(shù)減

20、去平均張數(shù)，題目就變成移動(dòng)正數(shù)，加到負(fù)數(shù)中，使大家都變成0，那就意味著成功了一半！ 從第i堆移動(dòng)-m張牌到第i+1堆，等價(jià)于從第i+1堆移動(dòng)m張牌到第i堆,步數(shù)是一樣的。 注意最左邊的0和最右邊的0不能算在內(nèi)，如0,0,1,-3,4,0,-1,0,0,擴(kuò)展1：,若題目中的紙牌排成一個(gè)環(huán)狀，應(yīng)如何處理呢？ 其中n=1000。,擴(kuò)展2：,有n個(gè)小朋友坐成一圈，每人有ai個(gè)糖果。每人只能給左右兩人傳遞糖果。每人每次傳遞一個(gè)糖果代價(jià)為1。求使所有人獲得均等糖果的最小代價(jià)。 【數(shù)據(jù)規(guī)?！?對(duì)于30%的數(shù)據(jù)n=1000； 對(duì)于100%的數(shù)據(jù)n=1000000,貪心的經(jīng)典應(yīng)用,（一）、三個(gè)區(qū)間上的問(wèn)題 1、

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

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

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