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

第五部分分治策略第一頁(yè)，共113頁(yè)。一、分治思想分治法，又叫分治策略，顧名思義，分而治之。它的基本思想：對(duì)于難以直接解決的規(guī)模較大的問題，把它分解成若干個(gè)能直接解決的相互獨(dú)立的子問題，遞歸求出各子問題的解，再合并子問題的解，得到原問題的解。通過減少問題的規(guī)模，逐步求解，能夠明顯降低解決問題的復(fù)雜度。第二頁(yè)，共113頁(yè)。二、分治法的適用條件能使用分治法解決的問題，它們一般具備以下幾個(gè)特征：①該問題可分解成若干相互獨(dú)立、規(guī)模較小的相同子問題；②子問題縮小到一定的程度就能輕易得到解；③子問題的解合并后，能得到原問題的解；分治法在信息學(xué)競(jìng)賽中應(yīng)用非常廣泛，使用分治策略能生成一些常用的算法和數(shù)據(jù)結(jié)構(gòu)，如快排、最優(yōu)二叉樹、線段樹等；還可以直接使用分治策略，解決一些規(guī)模很大、無法直接下手的問題。第三頁(yè)，共113頁(yè)。三、分治的三步驟①分解：將要解決的問題分解成若干個(gè)規(guī)模較小的同類子問題；②解決：當(dāng)子問題劃分得足夠小時(shí)，求解出子問題的解。③合并：將子問題的解逐層合并成原問題的解。第四頁(yè)，共113頁(yè)。分治算法設(shè)計(jì)過程圖第五頁(yè)，共113頁(yè)。在劃分問題時(shí)，可以采用遞歸策略，把一個(gè)大問題逐步分解成規(guī)模較小的子問題，直至可以直接求出子問題的解；再將子問題逐層合并，返回到頂層，得到原問題的解。根據(jù)分治策略的劃分原則，把原問題劃分成多少個(gè)子問題才合適呢？各個(gè)子問題的規(guī)模應(yīng)該多大才合適呢？一般來說，每次劃分成2個(gè)子問題，每個(gè)子問題的規(guī)模差不多最合適。合并解時(shí)要因題而異，有些問題遞歸分解完能直接得到原問題的解，有些問題需逐層合并，得到原問題的解。第六頁(yè)，共113頁(yè)。四、分治的框架結(jié)構(gòu)procedureDivide()beginif(問題不可分)then//解決begin

直接求解；返回問題的解；endelsebegin

對(duì)原問題進(jìn)行分治；//分解遞歸對(duì)每一個(gè)分治的部分進(jìn)行求解;//解決

歸并整個(gè)問題，得出全問題的解;//合并

endend;第七頁(yè)，共113頁(yè)。五、分治的典型應(yīng)用1、求最大值和最小值2、求方程的根3、二分查找4、歸并排序5、快速冪6、求解線性遞推關(guān)系7、棋盤覆蓋問題8、循環(huán)日程表問題9、尋找最近點(diǎn)對(duì)第八頁(yè)，共113頁(yè)。1、求最大值和最小值例題1：給n個(gè)數(shù)，求它們之中最大值和最小值，要求比較次數(shù)盡量小。分析：假設(shè)數(shù)據(jù)個(gè)數(shù)為n,存放在數(shù)組a[1..n]中?？梢灾苯舆M(jìn)行比較：minn:=a[1];maxx:=a[1];fori:=2tondoifa[i]>maxxthenmaxx:=a[i];elseifa[i]<minnthenminn:=a[i];使用這一算法，比較次數(shù)為2(n-1)。若n=10,則比較18次。第九頁(yè)，共113頁(yè)?！痉椒?】分治策略劃分：把n個(gè)數(shù)均分為兩半。即：劃分點(diǎn)為d=(r1+r2)/2，兩個(gè)區(qū)間為[r1,d]和[d+1,r2]。遞歸求解：求左半的最小值min1和最大值max1以及右半最小值min2和最大值max2。合并：max1與max2比較得到所有數(shù)的最大值為maxx；min1與min2比較得到所有數(shù)的最小值為minn。第十頁(yè)，共113頁(yè)。procedurepd(r1,r2:integer;varmaxx,minn:integer)beginvarmax1,min1,max2,min2,d:integer;

ifr1=r2thenbeginmaxx:=x[r1];minn:=x[r1];endelseifr2=r1+1thenbeginifx[r2]>x[r1]thenbeginmaxx:=x[r2];minn:=x[r1];endelsebeginmaxx:=x[r1];minn:=x[r2];endendelsebegind:=(r1+r2)/2;pd(r1,d,max1,min1);

pd(d+1,r2,max2,min2);

ifmax1>max2thenmaxx:=max1;elsemaxx:=max2;

ifmin1<min2thenminn:=min1;elseminn:=min2;

endend第十一頁(yè)，共113頁(yè)。2、求方程的根例題2：一元三次方程求解（NOIP2001）【題目描述】有形如：ax3+bx2+cx+d=0這樣的一個(gè)一元三次方程。給出該方程中各項(xiàng)的系數(shù)(a,b,c,d均為實(shí)數(shù))，并約定該方程存在三個(gè)不同實(shí)根(根的范圍在-100至100之間)，且根與根之差的絕對(duì)值>=1。要求由小到大依次在同一行輸出這三個(gè)實(shí)根(根與根之間留有空格)，并精確到小數(shù)點(diǎn)后4位?！疚募斎搿枯斎雰H一行，有四個(gè)數(shù)，依次為a、b、c、d【文件輸出】輸出也只有一行，即三個(gè)根(從小到大輸出)【樣例輸入】1-5-420【樣例輸入】-2.002.005.00第十二頁(yè)，共113頁(yè)。分析如果精確到小數(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ù)值。第十三頁(yè)，共113頁(yè)。分析A.當(dāng)已知區(qū)間(a,b)內(nèi)有一個(gè)根時(shí)；用二分法求根，若區(qū)間(a,b)內(nèi)有根，則必有f(a)*f(b)<0。重復(fù)執(zhí)行如下的過程：①、若a+0.00001>b或f((a+b)/2)=0，則可確定根為(a+b)/2并退出過程；②、若f(a)*f((a+b)/2)<0,則由題目給出的定理可知根在區(qū)間(a,(a+b)/2)中,故對(duì)區(qū)間重復(fù)該過程；③、若f(a)*f((a+b)/2)>0,則必然有f((a+b)/2)*f(b)<0,根在((a+b)/2,b)中,對(duì)此區(qū)間重復(fù)該過程。執(zhí)行完畢,就可以得到精確到0.0001的根。第十四頁(yè)，共113頁(yè)。分析B、求方程的所有三個(gè)實(shí)根所有的根的范圍都在-100至100之間，且根與根之差的絕對(duì)值>=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中所述的二分法迅速出找出解。如此可求出方程的所有的解。第十五頁(yè)，共113頁(yè)。核心參考代碼procedureDivide(x1,x2:double)Beginvarx0,y0,y1,y2:double;x0:=(x1+x2)div2;y1:=cal(x1);y2:=cal(x2);y0:=cal(x0);if(x2-x1<0.00001andy1*y2<0)thenbeginwrite((x2+x1)div2:0:4);exit;endif(y1*y0<0orx0-x1>1)thendivide(x1,x0);if(y0*y2<0orx2-x0>1)thendivide(x0,x2);End;第十六頁(yè)，共113頁(yè)。3、歸并排序歸并排序的基本思想：歸并排序充分應(yīng)用分治算法的策略，通過二分的思想，將n個(gè)數(shù)最終分成n個(gè)單獨(dú)的有序數(shù)列，每個(gè)數(shù)列中僅有一個(gè)數(shù)字；再將相鄰的兩列數(shù)據(jù)合并成一個(gè)有序數(shù)列；再重復(fù)上面的合并操作，直到合成一個(gè)有序數(shù)列。按照分治三步法來說：（1）劃分：把序列分成元素個(gè)數(shù)相等的兩半；（2）遞歸求解：把兩半分別排序；（3）合并：把兩個(gè)有序表合成一個(gè)有序表；第十七頁(yè)，共113頁(yè)。第十八頁(yè)，共113頁(yè)。分析顯然，前兩部分是很容易完成的，關(guān)鍵在于如何把兩個(gè)有序表合成一個(gè)。每次只需要把兩個(gè)有序表中當(dāng)前的最小元素加以比較，刪除較小元素并加入合并后的新表中。第十九頁(yè)，共113頁(yè)。核心參考代碼procedureMergeSort(left,right:integer)//歸并排序beginifleft=rightthenexit;//只有一個(gè)元素mid:=(left+right)div2;//找中間位

MergeSort(left,mid);//對(duì)左邊歸并

MergeSort(mid+1,right);//對(duì)右邊歸并

i:=left;j:=mid+1,p:=left;//合并左右while(i<=midandj<=right)do

if(a[i]>a[j])thenbegintemp[p]:=a[j];inc(p);inc(j);endelsebegintemp[p]:=a[i];inc(p);inc(i);endwhile(i<=mid)dobegintemp[p]:=a[i];inc(p);inc(i);endwhile(j<=right)dobegintemp[p]:=a[j];inc(p);inc(i);endfori:=lefttorightdoa[i]:=temp[i];

End;第二十頁(yè)，共113頁(yè)?！咀冃?】求逆序?qū)?shù)目例題3：求“逆序?qū)Α苯o定一整數(shù)數(shù)組A=(A1,A2,…An),若i<j且Ai>Aj,則<i,j>就為一個(gè)逆序?qū)?。例如?shù)組（3，1，4，5，2）的逆序?qū)τ?lt;3,1>,<3,2>,<4,2>,<5,2>。問題是，輸入n和A數(shù)組，統(tǒng)計(jì)逆序?qū)?shù)目。數(shù)據(jù)范圍：1<=n<=30000。第二十一頁(yè)，共113頁(yè)。方法1：樸素算法在看完試題以后，我們不難想到一個(gè)非常簡(jiǎn)單的算法——窮舉算法，即對(duì)數(shù)組中任意的兩個(gè)元素進(jìn)行判斷，看它們是不是構(gòu)成“逆序?qū)Α保虼诉@種算法的時(shí)間復(fù)雜度為O(N2)。c:=0;fori:=1ton-1doforj:=i+1tondoifa[i]>a[j]thenc:=c+1;時(shí)間效率不盡如人意…..問題出現(xiàn)在哪里呢？？第二十二頁(yè)，共113頁(yè)。求逆序?qū)Φ姆椒ǎ呵竽嫘驅(qū)τ卸喾N方法，目前使用比較廣泛且實(shí)現(xiàn)比較簡(jiǎn)單的主要有三種算法：1、歸并排序2、線段樹3、樹狀數(shù)組第二十三頁(yè)，共113頁(yè)。方法2：分治策略采用二分法求解:記數(shù)列a[st,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)表示一個(gè)數(shù)取自a[st,mid],另一個(gè)數(shù)取自a[mid+1,ed]所構(gòu)成的逆序?qū)?shù)目。第二十四頁(yè)，共113頁(yè)。和歸并排序一樣，劃分和遞歸求解都好辦，關(guān)鍵在于合并：如何求出i在左邊，而j在右邊的逆序?qū)?shù)目呢？統(tǒng)計(jì)的常見技巧是“分類”。我們按照j的不同把這些“跨越兩邊”的逆序?qū)M(jìn)行分類：只要對(duì)于右邊的每個(gè)j，統(tǒng)計(jì)左邊比它大的元素個(gè)數(shù)f(j)，則所有f(j)之和便是答案。幸運(yùn)的是，歸并排序可以幫助我們“順便”完成f(j)的計(jì)算：由于合并操作是從小到大進(jìn)行排序的，當(dāng)右邊的a[j]復(fù)制到T中時(shí)，左邊還沒有來得及復(fù)制到T的那些數(shù)就是左邊所有比a[j]大的數(shù)。此時(shí)累加器中加上左邊元素個(gè)數(shù)mid-i+1即可。即把“if(a[i]>a[j])thenbegintemp[p]:=a[j];inc(p);inc(j);end

改為“if(a[i]>a[j])thenbegintot:=tot+mid-i+1;temp[p]:=a[j];inc(p);inc(j);end第二十五頁(yè)，共113頁(yè)。4、二分查找【問題】給出從小到大排列的n個(gè)不同數(shù)a[1]~a[n]，試判斷元素x是否出現(xiàn)在表中。方法1：順序查找。即一個(gè)一個(gè)進(jìn)行尋找，時(shí)間復(fù)雜度為O(n)。這個(gè)方法并沒有用到“n個(gè)數(shù)從小到大排列”這一個(gè)關(guān)鍵條件，因而時(shí)間效率低下。第二十六頁(yè)，共113頁(yè)。方法2：二分查找只需要比較log2n個(gè)元素。假設(shè)需要在a[L]~a[r]中查找元素x。劃分：檢查某個(gè)元素a[m](L<=m<=r)，如果a[m]=x則查找成功，返回m。遞歸求解：如果a[m]>x，那么元素只可能在a[L]~a[m-1]中如果a[m]<x，那么元素只可能在a[m+1]~a[r]中。合并：不需要合并。第二十七頁(yè)，共113頁(yè)。實(shí)現(xiàn)方法1：二分查找的遞歸實(shí)現(xiàn)functionbsh(L,r,x:integer):integer;Beginvarm:integer;ifL>rexit(-1);m:=(L+r)div2;ifa[m]=xbsh:=m;elseifa[m]>xthenbsh:=bsh(L,m-1,x);elsebsh:=bsh(m+1,r,x);End;第二十八頁(yè)，共113頁(yè)。實(shí)現(xiàn)方法2：二分查找的非遞歸實(shí)現(xiàn)functionbsh(L,r,x:integer):integer;Beginvarm:integer;while(L<=r)dobeginm:=(L+r)div2;ifa[m]=xbeginbsh:=m;exit;endelseifa[m]>xthenr:=m-1elseL:=m+1;endbsh:=-1;//查找不成功End;第二十九頁(yè)，共113頁(yè)?！緮U(kuò)展1】二分查找求下界，即第一次出現(xiàn)的位置functionErfen(L,r,x:integer):integer;beginvarmid:integer;while(L<r)dobeginmid:=(L+r)div2;ifx<=a[mid]thenr:=midelseL:=mid+1;end;Erfen:=L;end;【擴(kuò)展2】二分查找求上界，即最后一次出現(xiàn)位置的后一個(gè)位置第三十頁(yè)，共113頁(yè)。【變形1】：奇怪的函數(shù)

【問題描述】使得xx達(dá)到或超過n位數(shù)字的最小正整數(shù)x是多少？【文件輸入】輸入一個(gè)正整數(shù)n?！疚募敵觥枯敵鍪沟脁x達(dá)到n位數(shù)字的最小正整數(shù)x。第三十一頁(yè)，共113頁(yè)?！咀冃?】：統(tǒng)計(jì)

【問題描述】給你一個(gè)有n(n<=100000)個(gè)整數(shù)的序列，接下來有m(m<=10000)個(gè)詢問，每個(gè)詢問為一個(gè)整數(shù)，需要你輸出在給出的序列中，此整數(shù)有多少個(gè)?第三十二頁(yè)，共113頁(yè)。【變形3】：查找等值點(diǎn)【問題描述】n個(gè)不同整數(shù)從小到大排序后放在數(shù)組A1~An中，是否存在i，使得Ai=i？若存在，試找到此點(diǎn)。第三十三頁(yè)，共113頁(yè)。第三十四頁(yè)，共113頁(yè)。5、快速冪【問題】計(jì)算anmodk的值

，其中n<=109。方法1：樸素算法。每次乘以a，時(shí)間復(fù)雜度O(n)。functionpower(a,n:integer):integer;beginvarx:integer;x:=1;fori:=1tondox:=x*a;power:=x;end;很明顯，此程序要超時(shí)。第三十五頁(yè)，共113頁(yè)。方法2：分治算法劃分：如果n是偶數(shù)，則考慮x=ndiv2否則考慮x=(n-1)div2遞歸求解：計(jì)算ax。合并：如果n是偶數(shù)，則an=(ax)2，否則an=(ax)2*a第三十六頁(yè)，共113頁(yè)。方法2：分治算法根據(jù)這個(gè)方法很容易寫出程序：functionpower(a,n:integer):integer;Beginifn=0beginpower:=1;exit;endelseifnmod2=1then//n為奇數(shù)的情況beginx:=power(a,(n-1)div2);power:=((x*x)modk*a)modk;endelsebegin//n為偶數(shù)的情況x:=power(a,ndiv2);power:=x*xmodk;end;End;第三十七頁(yè)，共113頁(yè)。方法3：用二進(jìn)制實(shí)現(xiàn)快速冪計(jì)算read(a,b,k);//輸入三個(gè)數(shù)

t:=b;whilet<>0dobegininc(len);c[len]:=tmod2;t:=tdiv2;end;//轉(zhuǎn)為二進(jìn)制

s:=1;fori:=lendownto1do//用二分法實(shí)現(xiàn)abmodkbegins:=s*smodk;ifc[i]=1thens:=((amodk)*s)modk;//是奇數(shù)end;writeln(s);//輸出abmodk第三十八頁(yè)，共113頁(yè)。6、求解線性遞推關(guān)系【例題】Fibonacci數(shù)【題目描述】Fibonacci數(shù)列定義為：f[i]=f[i-2]+f[i-1](i>2)，其中f[1]=1,f[2]=1?，F(xiàn)在請(qǐng)你求Fibonacci數(shù)列的第n項(xiàng)?！疚募斎搿枯斎胛募挥幸恍袨橐粋€(gè)整數(shù)n(1<=n<=2^31-1)?！疚募敵觥枯敵鑫募挥幸恍袨橐粋€(gè)整數(shù)，表示Fibonacci數(shù)列的第n項(xiàng)mod32768的值?！緲永斎搿?【樣例輸出】3【數(shù)據(jù)范圍】對(duì)于20%的數(shù)據(jù)，1<=n<=1000對(duì)于40%的數(shù)據(jù)，1<=n<=10000000對(duì)于100%的數(shù)據(jù)，1<=n<=2^31-1第三十九頁(yè)，共113頁(yè)。樸素算法O(n)，肯定超時(shí)procedureFib(n:integer)beginvari:integer;f[0]:=0;f[1]:=1;fori:=2tondof[i]:=f[i-1]+f[i-2];end;先復(fù)習(xí)矩陣乘法兩個(gè)2*2矩陣相乘的公式為第四十頁(yè)，共113頁(yè)?？捎帽对龇ㄔ贠(logn)時(shí)間內(nèi)求出冪(忽略高精度)第四十一頁(yè)，共113頁(yè)。擴(kuò)展練習(xí)：若f[i]=f[i-1]+f[i-2]+f[i-3]，如何計(jì)算求出f[n]?第四十二頁(yè)，共113頁(yè)。7、棋盤覆蓋問題第四十三頁(yè)，共113頁(yè)。分析第四十四頁(yè)，共113頁(yè)。8、循環(huán)日程表問題【例題】比賽安排【問題描述】設(shè)有2n(n<=6)個(gè)球隊(duì)進(jìn)行單循環(huán)比賽,計(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ì)1234

比賽1-23-4第一天

1-32-4第二天

1-42-3第三天【文件輸入】一個(gè)整數(shù)n。【文件輸出】輸出比賽安排表?！緲永斎搿?【樣例輸出】1-23-4

1-32-4

1-42-3第四十五頁(yè)，共113頁(yè)。分析1：遞歸形式實(shí)現(xiàn)由于N個(gè)運(yùn)動(dòng)員要進(jìn)行單循環(huán)比賽，且在N-1天內(nèi)要結(jié)束全部比賽，經(jīng)過分析，當(dāng)且僅當(dāng)N為2的整次冪時(shí)，問題才有解，當(dāng)然解是不唯一的。這樣可以將運(yùn)動(dòng)員分成兩組：1,2,…,N/2和N/2+1,N/2+2,…,N。給第一組運(yùn)動(dòng)員安排一個(gè)比賽日程，得到一個(gè)N/2階的方陣A1；同時(shí)給第二組的運(yùn)動(dòng)員安排一個(gè)比賽日程，同樣會(huì)得到一個(gè)N/2階的一個(gè)方陣A2?？紤]到比賽的性質(zhì)，設(shè)定第I個(gè)運(yùn)動(dòng)員在某一天的比賽對(duì)手為第K個(gè)運(yùn)動(dòng)員，則第K個(gè)運(yùn)動(dòng)員在同一天的比賽對(duì)手必然是第I個(gè)運(yùn)動(dòng)員，即若有A[I,J]=K，則A[K,J]=I。因此原問題的解(一個(gè)N階方陣)可以由分解后的兩個(gè)子問題的解，合并起來。同時(shí)每一個(gè)子問題又可以按照上述的二分法分解下去，直至每個(gè)組中僅有2個(gè)運(yùn)動(dòng)員時(shí)為止。第四十六頁(yè)，共113頁(yè)。procedurearrangment(K,N:integer);{從K號(hào)運(yùn)動(dòng)員起的共N員運(yùn)動(dòng)員單循環(huán)比賽日程表的過程}beginifn=2then{處理只有2名運(yùn)動(dòng)員的情況，遞歸終止條件}beginA[K,0]:=K;A[K,1]:=K+1;A[K+1,0]:=K+1;A[K+1,1]:=K;endelsebeginarrangment(K,Ndiv2);arrangment(K+Ndiv2,Ndiv2);{遞歸分解原問題與求解子問題}fori:=KtoK+(Ndiv2)–1do{合并子問題的解,構(gòu)造原問題的解A[i,j]}forj:=(Ndiv2)toN-1doA[i,j]:=A[i+(Ndiv2),j-(Ndiv2)];fori:=K+(Ndiv2)toK+N–1doforj:=(Ndiv2)toN-1doA[i,j]:=A[i-(Ndiv2),j-(Ndiv2)];end;end;方法1：遞歸形式實(shí)現(xiàn)第四十七頁(yè)，共113頁(yè)。初看此題，感覺無法下手，因?yàn)闆]有任何直接可用的算法和數(shù)據(jù)結(jié)構(gòu)。仔細(xì)分析，可以發(fā)現(xiàn)，將問題進(jìn)行分解，能找出規(guī)律。當(dāng)n=1時(shí)，共有2個(gè)球隊(duì)參賽，一天就可以比完。當(dāng)n=2時(shí)，共有4個(gè)球隊(duì)，需比賽3天。從2個(gè)球隊(duì)的比賽安排表中可以看出，左上角與右下角對(duì)稱，左下角與右上角對(duì)稱，左下角的值是由左上角值加n得到的。方法2：遞推實(shí)現(xiàn)第四十八頁(yè)，共113頁(yè)。read(n);m:=1;a[1,1]:=1;h:=1;fori:=1tondom=2*m;//比賽總隊(duì)數(shù)

while(h<=m)do//從一個(gè)球隊(duì)開始構(gòu)造

beginfori:=1tohdo//構(gòu)造其余三個(gè)方陣forj:=1tohdobegina[i,j+h]:=a[i,j]+h;//構(gòu)造右上角方陣

a[i+h,j]:=a[i,j+h];//構(gòu)造左下角方陣

a[i+h,j+h]:=a[i,j];//構(gòu)造右下角方陣

end;h:=h*2;end;核心參考代碼：第四十九頁(yè)，共113頁(yè)。9、尋找最近點(diǎn)對(duì)

【問題描述】給定平面上n(n<=60000)個(gè)點(diǎn),找出其中的一對(duì)點(diǎn)的距離,使得在這n個(gè)點(diǎn)的所有點(diǎn)對(duì)中,該距離為所有點(diǎn)對(duì)中最小的。第五十頁(yè)，共113頁(yè)。分析【問題簡(jiǎn)述】給定平面上n個(gè)點(diǎn)的坐標(biāo)，找出其中歐幾里德距離最近的兩個(gè)點(diǎn)?！痉椒?】枚舉算法。需要枚舉O(n2)個(gè)點(diǎn)對(duì)，每個(gè)距離的計(jì)算時(shí)間為O(1)，故總的時(shí)間復(fù)雜度為O(n2)。有沒有更好的算法呢？第五十一頁(yè)，共113頁(yè)?！痉椒?】分治算法

劃分：先按照X坐標(biāo)排序，把所有點(diǎn)劃分成個(gè)數(shù)盡量相等的兩部分，分別求最近點(diǎn)對(duì)，設(shè)距離分別為dL和dr。第五十二頁(yè)，共113頁(yè)。合并：令d=min{dL,dr}，則跨越兩邊的點(diǎn)對(duì)中，只有下面的豎條中的才有可能更近。需要檢查豎條里的所有點(diǎn)對(duì)嗎？第五十三頁(yè)，共113頁(yè)。從上往下看,

對(duì)于任何一個(gè)p,另一側(cè)可能與它組成更近的點(diǎn)對(duì)在一個(gè)正方形中,它最多只有4個(gè)點(diǎn)(否則這個(gè)方格中會(huì)有距離比d小的點(diǎn)對(duì))最壞情況(同一行的紅藍(lán)點(diǎn)幾乎重合),需要檢查接下來的7個(gè)點(diǎn)(紅藍(lán)點(diǎn)混在一起)時(shí)間復(fù)雜度O(nlogn)第五十四頁(yè)，共113頁(yè)?？偨Y(jié)歸納分治是一種解題的策略，它的基本思想是：“如果整個(gè)問題比較復(fù)雜，可以將問題分化，各個(gè)擊破?！狈种伟胺帧焙汀爸巍眱蓪雍x，如何分，分后如何“治”成為解決問題的關(guān)鍵所在不是所有的問題都可以采用分治，只有那些能將問題分成與原問題類似的子問題，并且歸并后符合原問題的性質(zhì)的問題，才能進(jìn)行分治分治可進(jìn)行二分，三分等等，具體怎么分，需看問題的性質(zhì)和分治后的效果。只有深刻地領(lǐng)會(huì)分治的思想，認(rèn)真分析分治后可能產(chǎn)生的預(yù)期效率，才能靈活地運(yùn)用分治思想解決實(shí)際問題。第五十五頁(yè)，共113頁(yè)。第六部分貪心策略第五十六頁(yè)，共113頁(yè)。一、貪心策略的基本思想定義：貪心法是一種解決最優(yōu)問題的策略。它是從問題的初始解出發(fā)，按照當(dāng)前最佳的選擇，把問題歸納為更小的相似的子問題，并使子問題最優(yōu)，再由子問題來推導(dǎo)出全局最優(yōu)解。使用貪心方法需要注意局部最優(yōu)與全局最優(yōu)的關(guān)系，選擇當(dāng)前狀態(tài)的局部最優(yōu)并不一定能推導(dǎo)出問題的全局最優(yōu)。第五十七頁(yè)，共113頁(yè)?！疽吭谝粋€(gè)N×M的方格陣中，每一格子賦予一個(gè)數(shù)值，規(guī)定每次移動(dòng)時(shí)只能向上或向右?，F(xiàn)試找出一條路徑，使其從左下角至右上角所經(jīng)過的數(shù)字之和最大。我們以2×3的矩陣為例：若按貪心策略求解，所得路徑為：1→3→4→6；若按動(dòng)態(tài)規(guī)劃求解，所得路徑為：1→2→10→6。第五十八頁(yè)，共113頁(yè)。二、貪心策略的特點(diǎn)

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)的問題都可以用貪心策略求解。因?yàn)樨澬耐敲つ康模枰褂酶硇缘姆椒ā獎(jiǎng)討B(tài)規(guī)劃（例如“0-1背包問題”與“部分背包問題”）第五十九頁(yè)，共113頁(yè)?！締栴}1】部分背包問題給定一個(gè)最大載重量為M的卡車和N種食品，有食鹽，白糖，大米等。已知第i種食品的最多擁有Wi公斤，其商品價(jià)值為Vi元/公斤，編程確定一個(gè)裝貨方案，使得裝入卡車中的所有物品總價(jià)值最大?！痉治觥恳?yàn)槊恳粋€(gè)物品都可以分割成單位塊，單位塊的利益越大，顯然總收益越大，所以它局部最優(yōu)滿足全局最優(yōu)，可以用貪心法解答。方法如下：先將單位塊收益按從大到小進(jìn)行排列，然后用循環(huán)從單位塊收益最大的取起，直到不能取為止便得到了最優(yōu)解。第六十頁(yè)，共113頁(yè)?！締栴}2】0/1背包問題給定一個(gè)最大載重量為M的卡車和N種動(dòng)物。已知第i種動(dòng)物的重量為Wi，其最大價(jià)值為Vi，設(shè)定M，Wi，Vi均為整數(shù)，編程確定一個(gè)裝貨方案，使得裝入卡車中的所有動(dòng)物總價(jià)值最大?！痉治觥堪簇澬姆ǎ好看芜x價(jià)格最大的裝載。很明顯有反例：設(shè)N=3,卡車最大載重量是100,三種動(dòng)物A、B、C的重量分別是40,50,70,其對(duì)應(yīng)的總價(jià)值分別是80、100、150。第六十一頁(yè)，共113頁(yè)。三、貪心策略與其他算法的區(qū)別

1.貪心與遞推：與遞推不同的是，貪心法中推進(jìn)的每一步不是依據(jù)某一固定的遞推式，而是當(dāng)前看似最佳的貪心決策，不斷的將問題歸納為更加小的相似的子問題。所以歸納、分析、選擇正確合適的貪心策略，是正確解決貪心問題的關(guān)鍵。2.貪心與動(dòng)態(tài)規(guī)劃：與動(dòng)態(tài)規(guī)劃不同的是，貪心是鼠目寸光；動(dòng)態(tài)規(guī)劃是統(tǒng)攬全局。第六十二頁(yè)，共113頁(yè)。四、貪心策略的證明貪心策略能否適用，關(guān)鍵看在貪心的策略下，局部的最優(yōu)解能否得到全局最優(yōu)解。要看是否得到最優(yōu)解，就要看貪心選擇特征的證明了。常用的證明法有反證法和構(gòu)造法。1.反證法：顧名思義，對(duì)于當(dāng)前的貪心策略，否定當(dāng)前的選擇，看看是否能得到最優(yōu)解，如果不能得到，說明當(dāng)前貪心策略是正確的；否則，當(dāng)前策略不正確，不可用。2.構(gòu)造法：對(duì)于題目給出的問題，用貪心策略時(shí)，把問題構(gòu)造成已知的算法或數(shù)據(jù)結(jié)構(gòu)，以此證明貪心策略是正確的。第六十三頁(yè)，共113頁(yè)。五、幾個(gè)簡(jiǎn)單的貪心例子

第六十四頁(yè)，共113頁(yè)。貪心策略第六十五頁(yè)，共113頁(yè)。例題1：排隊(duì)問題

【問題描述】在一個(gè)食堂，有n個(gè)人排隊(duì)買飯，每個(gè)人買飯需要的時(shí)間為Ti，請(qǐng)你找出一種排列次序，使每個(gè)人買飯的時(shí)間總和最小。【輸入文件】輸入文件共兩行，第一行為n；第二行分別表示第1個(gè)人到第n個(gè)人每人買飯的時(shí)間T1,T2…,Tn?！据敵鑫募枯敵鑫募H一行為買飯的時(shí)間總和?！緲永斎搿?5371910【樣例輸出】90第六十六頁(yè)，共113頁(yè)。【思路點(diǎn)撥】假設(shè)取水的人按照1...n的順序排列的，那么問題就轉(zhuǎn)化為求以下公式的最小值：

Total=T1+(T1+T2)+(T1+T2+T3)+...+(T1+T2+...+Tn)，對(duì)公式換個(gè)寫法：

Total=nT1+(n-1)T2+(n-2)T3...+2Tn-1+Tn

現(xiàn)在你是否發(fā)現(xiàn)一點(diǎn)什么呢？如果讓T1<=T2<=T3<=.....<=Tn，也就是把接水時(shí)間少的人盡可能排在前面，總的等待時(shí)間就最少了。問題的本質(zhì)就轉(zhuǎn)變?yōu)榘裯個(gè)等待時(shí)間按照非遞減的順序排序，求出總和即可。

【證明】反證法。假設(shè)這種排列不正確，則交換T2和T3，有：Total‘=nT1+(n-1)T3+(n-2)T2...+2Tn-1+Tn

由于T2<=T3，故Total‘>=Total，兩者相比較，可知有序的序列能得到最優(yōu)的方案。對(duì)于其他位置的改變可以采用同樣的方法證明。用反證法證明時(shí)，關(guān)鍵是證明反例不成立，由此推出原方案是最優(yōu)的。第六十七頁(yè)，共113頁(yè)。問題推廣1：排隊(duì)打水問題

【問題描述】有n個(gè)人在一個(gè)水龍頭前排隊(duì)接水，假如每個(gè)人接水的時(shí)間為Ti，請(qǐng)編程找出這n個(gè)人排隊(duì)的一種順序，使得這n個(gè)人的平均等待時(shí)間最小。【輸入文件】輸入文件共兩行，第一行為n；第二行分別表示第1個(gè)人到第n個(gè)人每人的接水時(shí)間T1,T2…,Tn?！据敵鑫募枯敵鑫募H一行為最小的平均等待時(shí)間?！緲永斎搿?5371910【樣例輸出】15第六十八頁(yè)，共113頁(yè)?！舅悸伏c(diǎn)撥】首先需要理解平均等待時(shí)間的概念。平均等待時(shí)間就是每個(gè)人的等待時(shí)間之和再除以n，因?yàn)閚是個(gè)常數(shù)，所有等待時(shí)間之和最小也就等同于平均等待時(shí)間最小。這樣就轉(zhuǎn)化為前面的問題了

第六十九頁(yè)，共113頁(yè)。問題推廣2：排隊(duì)打水問題【問題描述】有n個(gè)人排隊(duì)到r個(gè)水龍頭去打水，他們裝滿水桶的時(shí)間T1、T2…,Tn為整數(shù)且各不相等，應(yīng)如何安排他們的打水順序才能使他們總共花費(fèi)的時(shí)間最少？【文件輸入】輸入文件共計(jì)兩行，第一行n，r(n<=500,r<=75)，第二行為n個(gè)人打水所用的時(shí)間Ti(Ti<=100)；【文件輸出】輸出文件只有一行為n個(gè)人打完水的最少總共花費(fèi)時(shí)間。【樣例輸入】321234【樣例輸出】13第七十頁(yè)，共113頁(yè)。例題2：打包

某工廠生產(chǎn)出的產(chǎn)品都要被打包放入正四棱柱的盒子內(nèi)，所有盒子的高度為h，但地面尺寸不同，可以為1x1、2x2、3x3、4x4、5x5、6x6。如下圖所示。這些盒子將被放入高度為h，地面尺寸為6x6的箱子中。為了降低運(yùn)送成本，工廠希望盡量減少箱子的數(shù)量。如果有一個(gè)好算法，能使箱子的數(shù)量降到最低，這將給工廠節(jié)省不少的資金。請(qǐng)你編寫一個(gè)程序。

第七十一頁(yè)，共113頁(yè)。分析第七十二頁(yè)，共113頁(yè)。分析第七十三頁(yè)，共113頁(yè)。例題3:均分紙牌（NOIP2002）有N堆紙牌，編號(hào)分別為1,2,…,N。每堆上有若干張，但紙牌總數(shù)必為N的倍數(shù)?？梢栽谌我欢焉先∪粲趶埣埮疲缓笠苿?dòng)。

移牌規(guī)則為：在編號(hào)為1堆上取的紙牌，只能移到編號(hào)為2的堆上；在編號(hào)為N的堆上取的紙牌，只能移到編號(hào)為N-1的堆上；其他堆上取的紙牌，可以移到相鄰左邊或右邊的堆上。

現(xiàn)在要求找出一種移動(dòng)方法，用最少的移動(dòng)次數(shù)使每堆上紙牌數(shù)都一樣多。

例如N=4，4堆紙牌數(shù)分別為：①9②8③17④6

移動(dòng)3次可達(dá)到目的：從③取4張牌放到④(981310)->從③取3張牌放到②(9111010)->從②取1張牌放到①(10101010）。第七十四頁(yè)，共113頁(yè)?！疚募斎搿康谝恍袨橐粋€(gè)整數(shù)N(N堆紙牌,1<=N<=100)，第二行為n個(gè)用空格分開的整數(shù)，依次為A1A2…An(N堆紙牌，每堆紙牌初始數(shù)，l<=Ai<=10000)。【文件輸出】所有堆均達(dá)到相等時(shí)的最少移動(dòng)次數(shù)?！緲永斎搿?98176【樣例輸出】3第七十五頁(yè)，共113頁(yè)。分析：【試題分析】我們要使移動(dòng)次數(shù)最少，就是要把浪費(fèi)降至零。通過對(duì)具體情況的分析，可以看出在某相鄰的兩堆之間移動(dòng)兩次或兩次以上，是一種浪費(fèi)，因?yàn)槲覀兛梢园阉鼈兒喜橐淮位蛄愦?。【思路點(diǎn)撥】如果你想到把每堆牌的張數(shù)減去平均張數(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

第七十六頁(yè)，共113頁(yè)。擴(kuò)展1：（NOIP模擬試題）若題目中的紙牌排成一個(gè)環(huán)狀，應(yīng)如何處理呢？其中n<=1000。第七十七頁(yè)，共113頁(yè)。擴(kuò)展2：（2011重慶省選）有n個(gè)小朋友坐成一圈，每人有ai個(gè)糖果。每人只能給左右兩人傳遞糖果。每人每次傳遞一個(gè)糖果代價(jià)為1。求使所有人獲得均等糖果的最小代價(jià)?！緮?shù)據(jù)規(guī)模】對(duì)于30%的數(shù)據(jù)n<=1000；對(duì)于100%的數(shù)據(jù)n<=1000000

第七十八頁(yè)，共113頁(yè)。例題4:射擊比賽（CEOI1997）

我們假設(shè)射擊的目標(biāo)是一個(gè)由R*C(2≤R≤C≤1000)個(gè)小方格組成的矩形網(wǎng)格。網(wǎng)格中每一列恰有2個(gè)白色的小方格和R-2個(gè)黑色的小方格。定義網(wǎng)格的行從頂至底編號(hào)為1~R，列從左至右編號(hào)為1~C。射擊者可射擊C次。在連續(xù)的C次射擊中，若每列恰好有一個(gè)白色的方格被射中，且不存在無白色方格被射中的行，這樣的射擊才是正確的。問題是，如果存在正確的射擊方法，則要求找到它。第七十九頁(yè)，共113頁(yè)。例如考慮如下目標(biāo)：由上圖可以看出，在每列中依次射中的行坐標(biāo)為2,3,1,4?，F(xiàn)在要求你編程計(jì)算出是否有正確的射擊方法。根據(jù)題設(shè)條件，射擊的選擇有2C種，符合要求的卻很少。要解決問題，還需從正確的射擊方法的特征入手。第八十頁(yè)，共113頁(yè)?！痉椒?】網(wǎng)絡(luò)流算法我們將表示列的點(diǎn)編號(hào)為1到C，表示行的點(diǎn)編號(hào)為C+1到C+R，如果一個(gè)白色方格處在第i行第j列，那么從點(diǎn)j向點(diǎn)C+i連一條弧，弧的容量為1。再增設(shè)一個(gè)源點(diǎn)S，從點(diǎn)S往點(diǎn)1到C間各連一條弧，弧的容量為1，又設(shè)一個(gè)匯點(diǎn)T，從點(diǎn)C+1到點(diǎn)C+R向匯點(diǎn)T連一條弧，弧的容量為1，那么從源點(diǎn)S到匯點(diǎn)T求最大流，求出的最大流量即為最多可以射擊到的行數(shù)。各條流的路線則描述了具體的射擊方案。顯然，如果用網(wǎng)絡(luò)流求出的最大流量比R小，則問題無解，否則我們可以根據(jù)網(wǎng)絡(luò)流的結(jié)果求出該二分圖的具體匹配方案。第八十一頁(yè)，共113頁(yè)。紅色的連線流量為1藍(lán)色的連線流量為0選擇的射擊格即為：(1,3),(2,1),(3,2),(4,4)S21432143T列:行:源:匯:第八十二頁(yè)，共113頁(yè)。網(wǎng)絡(luò)流算法經(jīng)過優(yōu)化，時(shí)間復(fù)雜度可以達(dá)到O(C*(n+4C+4R))上述網(wǎng)絡(luò)流算法雖然可以通過全部數(shù)據(jù)，但編程復(fù)雜度很高，而且極易出錯(cuò)，一不小心就會(huì)因?yàn)橐粋€(gè)小錯(cuò)誤影響整個(gè)程序。第八十三頁(yè)，共113頁(yè)。【方法二】貪心方法

1、統(tǒng)計(jì)所有行包含的白格數(shù)

2、從還沒有射擊格的行中選出一個(gè)白格數(shù)最少的

3、檢查所選的行（1）若所選行的白格數(shù)為0，則輸出無解；（2）否則從所選行的白格中任選一個(gè)作為射擊格，并將與該格同列的另一個(gè)白格所處行的白格數(shù)減1

4、返回到第2步，直到所有的行都有射擊格。

5、若還有列沒有選射擊格，則在該列任選一白格作為射擊格即可第八十四頁(yè)，共113頁(yè)。上面的貪心方法非常高效：時(shí)間復(fù)雜度為O(RC)，如果在程序中使用堆優(yōu)化，時(shí)間復(fù)雜度將降為O(Rlog2C)?？臻g復(fù)雜度是線性的，而且非常容易實(shí)現(xiàn)?，F(xiàn)在關(guān)鍵的問題就是——如何證明它的正確性？第八十五頁(yè)，共113頁(yè)。證明：用h[i]表示第i行的白格數(shù)。如果最開始的時(shí)候：①min{h[i]}=0：第i行已經(jīng)沒有辦法找到可作為射擊格的白格，那么問題只能無解。②min{h[i]}=1：那么第i行的這一個(gè)白格必須要作為射擊格，否則將因第i行沒有射擊格而造成問題無解。③min{h[i]}≥2：那么在這一行任選一個(gè)白格,頂多只會(huì)造成剩余行中有一行h值為1,再處理那一行，最多也只會(huì)再造成剩余行中有一行h值為1，如此往復(fù),將保持h值為1的行數(shù)不超過1行，最后最壞的情況也是造成最后一行的h值為1,繼續(xù)下去所有行就都已選取了射擊格了。因此，如果原問題有解，該貪心方法一定能找到一種正確的方案。由此可以證明，此貪心方法是正確的。確定貪心標(biāo)準(zhǔn)。第八十六頁(yè)，共113頁(yè)。六、貪心的經(jīng)典應(yīng)用

（一）、三個(gè)區(qū)間上的問題1、選擇不相交區(qū)間問題2、區(qū)間選點(diǎn)問題3、區(qū)間覆蓋問題（二）、兩個(gè)調(diào)度問題1、流水作業(yè)調(diào)度問題2、帶限期和罰款的單位時(shí)間任務(wù)調(diào)度（三）Huffman編碼

（四）最優(yōu)合并問題

第八十七頁(yè)，共113頁(yè)。1、選擇不相交區(qū)間問題給定n個(gè)開區(qū)間(ai,bi)，選擇盡量多個(gè)區(qū)間，使得這些區(qū)間兩兩沒有公共點(diǎn)?！舅惴▽?shí)現(xiàn)】首先按照b1<=b2<=…<=bn的順序排序，依次考慮各個(gè)活動(dòng)，如果沒有和已經(jīng)選擇的活動(dòng)沖突，就選；否則就不選。

貪心策略：取滿足條件的第一個(gè)區(qū)間；

【正確性】：如果不選b1，假設(shè)第一個(gè)選擇的是bi，則如果bi和b1不交叉則多選一個(gè)b1更劃算；如果交叉則把bi換成b1不影響后續(xù)選擇。（一）、三個(gè)區(qū)間上的問題第八十八頁(yè)，共113頁(yè)。【樣例輸入】6346713255647【樣例輸出】4

按照b[i]從小到大排序后的結(jié)果為：133425564767選擇的區(qū)間為：

13345667第八十九頁(yè)，共113頁(yè)。例題5：活動(dòng)安排設(shè)有n個(gè)活動(dòng)，每個(gè)活動(dòng)都要求使用同一資源，如演講會(huì)場(chǎng)等，而在同一時(shí)間內(nèi)只有一個(gè)活動(dòng)能使用這一資源。每個(gè)活動(dòng)i都有一個(gè)要求使用該資源的起始時(shí)間si和一個(gè)結(jié)束時(shí)間fi，且si<fi。如果選擇了活動(dòng)i，則它在半開時(shí)間區(qū)間[si,fi)內(nèi)占用資源。若區(qū)間[si,fi)與區(qū)間[sj,fj)不相交，則稱活動(dòng)i與活動(dòng)j是相容的。也就是說，當(dāng)fi>=sj或fj>=si時(shí)，活動(dòng)i與活動(dòng)j相容。選擇出由互相兼容的活動(dòng)組成的最大集合。第九十頁(yè)，共113頁(yè)。2、區(qū)間選點(diǎn)問題給定n個(gè)閉區(qū)間[ai,bi]，在數(shù)軸上選盡量少的點(diǎn)，使得每個(gè)區(qū)間內(nèi)都至少有兩個(gè)不同點(diǎn)（不同區(qū)間內(nèi)含的點(diǎn)可以是同一個(gè)）?！舅惴ā浚合劝凑账袇^(qū)間的結(jié)束位置從小到大排序。從區(qū)間1到區(qū)間n進(jìn)行循環(huán)，對(duì)于當(dāng)前區(qū)間，若已選中的數(shù)不能覆蓋它，則從區(qū)間末尾向前掃描，若當(dāng)前數(shù)未選中出現(xiàn)，則將該數(shù)標(biāo)記為已選中，直至使選中的數(shù)能滿足該區(qū)間要求為止。第九十一頁(yè)，共113頁(yè)。【樣例輸入】436240247【樣例輸出】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ù)對(duì)以后區(qū)間的影響越大，即它在以后區(qū)間出現(xiàn)的可能性越大，但未經(jīng)嚴(yán)格數(shù)學(xué)證明。第九十二頁(yè)，共113頁(yè)。例題6：種樹（NOIP模擬試題）

一條街的一邊有幾座房子。因?yàn)榄h(huán)保原因居民想要在路邊種些樹。路邊的地區(qū)被分割成塊，并被編號(hào)為1..n。每個(gè)塊大小為一個(gè)單位尺寸并最多可種一棵樹。每個(gè)居民想在門前種些樹并指定了三個(gè)號(hào)碼b,e,t。這三個(gè)數(shù)表示該居民想在b和e之間最少種t棵樹。當(dāng)然b<=e,居民必須保證在指定地區(qū)不能種多于地區(qū)被分割成塊數(shù)的樹，即要求t<=e-b+1。允許居民想種樹的各自區(qū)域可以交叉。出于資金短缺的原因,環(huán)保部門請(qǐng)你求出能夠滿足所有居民的要求,需要種樹的最少數(shù)量。第九十三頁(yè)，共113頁(yè)。樣例輸入:94142462892352樣例輸出：5第九十四頁(yè)，共113頁(yè)。分析方法1：貪心策略方法2：利用差分約束系統(tǒng)解決方法3：使用樹狀數(shù)組第九十五頁(yè)，共113頁(yè)。3、區(qū)間覆蓋問題給n個(gè)閉區(qū)間[ai,bi]，選擇盡量少的區(qū)間覆蓋一條指定線段[s,t]。

本題的突破口仍然是區(qū)間包含和排序掃描，不過先要進(jìn)行一次預(yù)處理。每個(gè)區(qū)間在[s,t]外的部分都應(yīng)該預(yù)先被切掉，因?yàn)樗鼈兊拇嬖谑呛翢o意義的。在預(yù)處理后，在相互包含的情況下，小區(qū)間顯然不應(yīng)該考慮。第九十六頁(yè)，共113頁(yè)。把各區(qū)間按照a從小到大排序，若a相同，則b從大到小排序（自動(dòng)處理掉區(qū)間包含）。注意：若區(qū)間1的起點(diǎn)大于s，則無解（因?yàn)槠渌麉^(qū)間的起點(diǎn)更大，不可能覆蓋到s點(diǎn)），否則選擇起點(diǎn)在s的最長(zhǎng)區(qū)間[ai,bi]后，新的起點(diǎn)應(yīng)該設(shè)置為bi，并且忽略所有區(qū)間在bi之前的部分，就像預(yù)處理一樣。雖然貪心策略比上題復(fù)雜，但是仍然只需要一次掃描，如下圖，s為當(dāng)前有效起點(diǎn)（此前部分已被覆蓋），則應(yīng)該選擇區(qū)間2。貪心思想：在某個(gè)時(shí)刻s，找一個(gè)滿足a[i]>=s的b[i]的最大值即可。

第九十七頁(yè)，共113頁(yè)?！緲永斎搿?2514383107104613【樣例輸出】14310

按照b[i]從小到大排序后的結(jié)果為：1413253103846710第九十八頁(yè)，共113頁(yè)。例題7：區(qū)間（SDOI2005）

現(xiàn)給定n