NOIP基礎(chǔ)算法綜合-分治與貪心第四部分分治策略一、分治思想分治法，又叫分治策略，顧名思義，分而治之。它的基本思想為：對于難以直接解決的規(guī)模較大的問題，把它分解成若干個(gè)能直接解決的相互獨(dú)立的子問題，遞歸求出各子問題的解，再合并子問題的解，得到原問題的解。通過減少問題的規(guī)模，逐步求解，能夠明顯降低解決問題的復(fù)雜度。二、分治法的適用條件能使用分治法解決的問題，它們一般具備以下幾個(gè)特征：①該問題可以分解成若干相互獨(dú)立、規(guī)模較小的相同子問題；②子問題縮小到一定的程度能輕易得到解；③子問題的解合并后，能得到原問題的解；分治法在信息學(xué)競賽中應(yīng)用非常廣泛，使用分治策略能生成一些常用的算法和數(shù)據(jù)結(jié)構(gòu)，如快排、最優(yōu)二叉樹、線段樹等；還可以直接使用分治策略，解決一些規(guī)模很大、無法直接下手的問題。三、分治的三步驟①分解：將要解決的問題分解成若干個(gè)規(guī)模較小的同類子問題；②解決：當(dāng)子問題劃分得足夠小時(shí)，求解出子問題的解。③合并：將子問題的解逐層合并成原問題的解。分治算法設(shè)計(jì)過程圖分治思想由分治法所得到的子問題與原問題具有相同的類型。如果得到的子問題相對來說還太大，則可反復(fù)使用分治策略將這些子問題分成更小的同類型子問題，直至產(chǎn)生出不用進(jìn)一步細(xì)分就可求解的子問題。分治求解可用一個(gè)遞歸過程來表示。要使分治算法效率高，關(guān)鍵在于如何分割？一般地，出于一種平衡原則，總是把大問題分成K個(gè)規(guī)模盡可能相等的子問題，但也有例外，如求表的最大最小元問題的算法，當(dāng)n＝6時(shí)，等分定量成兩個(gè)規(guī)模為3的子表L1和L2不是最佳分割。一般來講，都是2分為主。四、分治的框架結(jié)構(gòu)if(問題不可分){直接求解；返回問題的解；}else{對原問題進(jìn)行分治；遞歸對每一個(gè)分治的部分求解;

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

}

五、分治的典型應(yīng)用1、求最大值和最小值2、非線性方程求根3、二分查找4、歸并排序5、快速冪6、求解線性遞推關(guān)系7、棋盤覆蓋問題8、循環(huán)日程表問題9、尋找最近點(diǎn)對1、求最大值和最小值例題1：給n個(gè)實(shí)數(shù)，求它們之中最大值和最小值，要求比較次數(shù)盡量小。分析：假設(shè)數(shù)據(jù)個(gè)數(shù)為n,存放在數(shù)組a[1..n]中?？梢灾苯舆M(jìn)行比較：minn=a[1];maxx=a[1];for(i=2;i<=n;i++)if(a[i]>maxx)maxx=a[i];elseif(a[i]<minn)minn=a[i];使用這一算法，比較次數(shù)為2(n-1)。若n=10,則比較18次。用分治法解決這個(gè)問題就是把集合a分成a1,a2兩個(gè)子集，每個(gè)子集有n/2個(gè)元素，應(yīng)用遞歸結(jié)構(gòu)找出兩個(gè)子集的最大元和最小元，比較得到的兩個(gè)最大元和最小元即可得到整個(gè)集合a中的最大元和最小元。劃分：把n個(gè)數(shù)均分為兩半。即：劃分點(diǎn)為d=(r1+r2)/2，兩個(gè)區(qū)間為[r1,d]和[d+1,r2]。遞歸求解：求左半的最小值min1和最大值max1以及右半最小值min2和最大值max2。合并：所有數(shù)的最大值為maxx，最小值為minn。核心代碼voidpd(intr1,intr2,int&maxx,int&minn){intmax1,min1,max2,min2,d;

if(r1==r2){maxx=minn=x[r1];}elseif(r2==r1+1){if(x[r2]>x[r1]){maxx=x[r2];minn=x[r1];}else{maxx=x[r1];minn=x[r2];}}else{d=(r1+r2)/2;pd(r1,d,max1,min1);

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

if(max1>max2)maxx=max1;elsemaxx=max2;

if(min1<min2)minn=min1;elseminn=min2;

}}【思考試題】最大值最小化【問題描述】把一個(gè)包含n個(gè)正整數(shù)的序列劃分成m個(gè)連續(xù)的子序列(每個(gè)正整數(shù)恰好屬于一個(gè)序列)。設(shè)第i個(gè)序列的各數(shù)之和為S(i)，你的任務(wù)是讓所有的S(i)的最大值盡量小。例如序列123254劃分成3個(gè)序列的最優(yōu)方案為123|25|4，其中S(1)=6，S(2)=7，S(3)=4，最大值為7；如果劃分成12|32|54，則最大值為9；不如剛才的好。n<=10^6，所有數(shù)字之和不超過10^9。2、非線性方程求根【例題2】一元三次方程的解【題目描述】有形如：ax3+bx2+cx+d=0這樣的一個(gè)一元三次方程。給出該方程中各項(xiàng)的系數(shù)(a,b,c,d均為實(shí)數(shù))，并約定該方程存在三個(gè)不同實(shí)根(根的范圍在-100至100之間)，且根與根之差的絕對值>=1。要求由小到大依次在同一行輸出這三個(gè)實(shí)根(根與根之間留有空格)，并精確到小數(shù)點(diǎn)后4位?！疚募斎搿枯斎雰H一行，有四個(gè)數(shù)，依次為a、b、c、d【文件輸出】輸出也只有一行，即三個(gè)根(從小到大輸出)【樣例輸入】1-5-420【樣例輸入】-2.002.005.00分析如果精確到小數(shù)點(diǎn)后兩位，可用簡單枚舉法：將x從-100.00到100.00（步長0.01）逐一枚舉，得到20000個(gè)f(x)，取其值與0最接近的三個(gè)f(x)，對應(yīng)的x即為答案。而題目已改成精度為小數(shù)點(diǎn)后4位，枚舉算法時(shí)間復(fù)雜度將達(dá)不到要求。直接使用求根公式，極為復(fù)雜。加上本題的提示給我們以啟迪：采用二分法逐漸縮小根的范圍，從而得到根的某精度的數(shù)值分析A.當(dāng)已知區(qū)間(a,b)內(nèi)有一個(gè)根時(shí)；用二分法求根，若區(qū)間(a,b)內(nèi)有根，則必有f(a)*f(b)<0。重復(fù)執(zhí)行如下的過程：(1).若a+0.0001>b或f((a+b)/2)=0，則可確定根為(a+b)/2并退出過程；(2).若f(a)*f((a+b)/2)<0,則由題目給出的定理可知根在區(qū)間(a,(a+b)/2)中,故對區(qū)間重復(fù)該過程；(3).若f(a)*f((a+b)/2)>0,則必然有f((a+b)/2)*f(b)<0,根在((a+b)/2,b)中,對此區(qū)間重復(fù)該過程。執(zhí)行完畢,就可以得到精確到0.0001的根。分析B、求方程的所有三個(gè)實(shí)根所有的根的范圍都在-100至100之間，且根與根之差的絕對值>=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中所述的二分法迅速出找出解。如此可求出方程的所有的解。核心參考代碼voiddivide(doublex1,doublex2){doublex0,y0,y1,y2;x0=(x1+x2)/2;y1=cal(x1);y2=cal(x2);y0=cal(x0);if(x2-x1<0.00001&&y1*y2<0){printf("%.4f",(x2+x1)/2);return;}if(y1*y0<0||x0-x1>1)divide(x1,x0);if(y0*y2<0||x2-x0>1)divide(x0,x2);}3、歸并排序歸并排序的基本思想：歸并排序充分應(yīng)用分治算法的策略，將n個(gè)數(shù)分成n個(gè)單獨(dú)的有序數(shù)列，每個(gè)數(shù)列中僅有一個(gè)數(shù)字；再將相鄰的兩列數(shù)據(jù)合并成一個(gè)有序數(shù)列，每個(gè)數(shù)列中有2個(gè)數(shù)；再重復(fù)上面的合并操作，直到合成一個(gè)有序數(shù)列。按照分治三步法來說，歸并過程為：（1）劃分：把序列分成元素個(gè)數(shù)相等的兩半；（2）遞歸求解：把兩半分別排序；（3）合并：把兩個(gè)有序表合成一個(gè)；分析顯然，前兩部分是很容易完成的，關(guān)鍵在于如何把兩個(gè)有序表合成一個(gè)。每次只需要把兩個(gè)序列中當(dāng)前的最小元素加以比較，刪除較小元素并加入合并后的新表。核心參考代碼inttemp[maxn];//輔助空間voidMergeSort(intleft,intright)//對區(qū)間left---right進(jìn)行歸并排序{if(left==right)return;//只有一個(gè)元素mid=(left+right)/2;//找中間位

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

MergeSort(mid+1,right);//對右邊歸并i=left,j=mid+1,p=left;//合并左右while(i<=mid&&j<=right)

if(a[i]>a[j])temp[p++]=a[j++];elsetemp[p++]=a[i++];while(i<=mid)temp[p++]=a[i++];while(j<=right)temp[p++]=a[j++];for(i=left;i<=right;i++)a[i]=temp[i];}

【變形1】逆序?qū)?shù)目例題：求“逆序?qū)Α?。給定一整數(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。樸素算法原始的解決方案（雙重循環(huán)）C:=0;Fori:=1ton-1doforj:=i+1tondoifa[i]>a[j]thenc:=c+1;時(shí)間復(fù)雜度為O(n2)分治算法：采用二分法求解:記數(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]的逆序?qū)?shù)目。和歸并排序一樣，劃分和遞歸求解都好辦，關(guān)鍵在于合并：如何求出i在左邊，而j在右邊的逆序?qū)?shù)目呢？統(tǒng)計(jì)的常見技巧是“分類”。我們按照j的不同把這些“跨越兩邊”的逆序?qū)M(jìn)行分類：只要對于右邊的每個(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])temp[p++]=a[j++];”改為“if(a[i]>a[j]){tot=tot+mid-i+1;temp[p++]=a[j++];}”。4、二分查找【問題描述】給出從小到大排列的n個(gè)不同數(shù)a[0]~a[n-1]，試判斷元素x是否出現(xiàn)在表中。方法1：順序查找：方法是一個(gè)個(gè)尋找，時(shí)間復(fù)雜度為O(n)。這個(gè)方法并沒有用到“n個(gè)數(shù)從小到大排列”這一個(gè)關(guān)鍵條件，因而時(shí)間效率低下。方法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]中。合并：不需要合并。方法1：二分查找的遞歸實(shí)現(xiàn)intbsearch(intL,intr,intx){if(L>r)return-1;intm=(L+r)/2;if(a[m]==x)returnm;elseif(a[m]>x)returnbsearch(L,m-1,x);elsereturnbsearch(m+1,r,x);}

方法2：二分查找的非遞歸實(shí)現(xiàn)：intbsearch(intL,intr,intx){intm;while(L<=r){m=(L+r)/2;if(a[m]==x)returnm;elseif(a[m]>x)r=m–1;elseL=m+1;}return-1;//查找不成功}【擴(kuò)展1】二分查找求下界，即第一次出現(xiàn)的位置intErfen(intL,intr,intx){intmid;while(L<r){mid=(L+r)/2;if(x<=a[mid])r=mid;elseL=mid+1;}returnL;}【擴(kuò)展2】二分查找求上界，即最后一次出現(xiàn)位置的后一個(gè)位置【思考題目】給出n個(gè)整數(shù)和m個(gè)詢問，對于每個(gè)詢問(a,b)，輸出閉區(qū)間[a,b]內(nèi)的整數(shù)c的個(gè)數(shù)。【思路點(diǎn)撥】①先把所有的數(shù)據(jù)從小到大排序；②二分查找求下界，即第一次出現(xiàn)的位置low；③二分查找求上界，即最后一次出現(xiàn)位置的后一個(gè)位置high；④答案區(qū)間為：ans=high-low【變形1】查找等值點(diǎn)【問題描述】n個(gè)不同整數(shù)從小到大排序后放在數(shù)組A0~An-1中，是否存在i，使得Ai=i？若存在，試找到此點(diǎn)。5、快速冪【問題描述】計(jì)算an%k

，n<=109。方法1：樸素算法。每次乘以a，時(shí)間復(fù)雜度O(n)。intpower(inta,intn){intx=1;for(i=1;i<=n;i++)x*=a;returnx;}方法2：分治算法

劃分：如果n是偶數(shù)，考慮k=n/2，否則考慮k=(n-1)/2遞歸求解：計(jì)算ak。合并：如果n是偶數(shù)，則an=(ak)2，否則an=(ak)2*a根據(jù)這個(gè)方法很容易寫出程序：intpower(inta,intn){if(n==0)return1;elseif(n%2==1){intx=power(a,(n-1)/2);return((x*x)%k*a)%k;}else{intx=power(a,n/2);return(x*x)%k;}}方法3：用二進(jìn)制實(shí)現(xiàn)快速冪計(jì)算

cin>>b>>p>>k;//輸入三個(gè)數(shù)

t=p;while(t!=0){len++;a[len]=t%2;t=t/2;}//轉(zhuǎn)為二進(jìn)制

ans=1;for(i=len;i>=1;i--)//用二分法實(shí)現(xiàn)b^pmodk{ans=ans*ans%k;if(a[i]==1)ans=b%k*ans%k;//如果是奇數(shù)，就多乘b}cout<<ans<<endl;//輸出b^pmodk6、求解線性遞推關(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)在請你求Fibonacci數(shù)列的第n項(xiàng)?！疚募斎搿枯斎胛募挥幸恍袨橐粋€(gè)整數(shù)n(1<=n<=2^31-1)。【文件輸出】輸出文件只有一行為一個(gè)整數(shù)，表示Fibonacci數(shù)列的第n項(xiàng)mod32768的值?！緲永斎搿?【樣例輸出】3【數(shù)據(jù)范圍】對于20%的數(shù)據(jù)，1<=n<=1000對于40%的數(shù)據(jù)，1<=n<=10000000對于100%的數(shù)據(jù)，1<=n<=2^31-1分析枚舉，肯定超時(shí)voidprecalc_fib(intn){f[0]=0;f[1]=1;for(inti=2;i<=n;i++)f[i]=f[i-1]+f[i-2];}先復(fù)習(xí)矩陣乘法?兩個(gè)2*2矩陣相乘的公式為?可用倍增法在O(logn)時(shí)間內(nèi)求出冪(忽略高精度)一般情形7、棋盤覆蓋問題分析8、循環(huán)日程表問題【例題】比賽安排【問題描述】設(shè)有2n(n<=6)個(gè)球隊(duì)進(jìn)行單循環(huán)比賽,計(jì)劃在2n-1天內(nèi)完成，每個(gè)隊(duì)每天進(jìn)行一場比賽。設(shè)計(jì)一個(gè)比賽的安排，使在2n-1天內(nèi)每個(gè)隊(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à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ì)的比賽安排表中可以看出，左上角與右下角對稱，左下角與右上角對稱，左下角的值是由左上角值加n得到的。cin>>n;m=1;a[1][1]=1;h=1;m=1<<n;//比賽總隊(duì)數(shù)

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

{for(i=1;i<=h;i++)for(j=1;j<=h;j++){a[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)造右下角方陣

}h=h*2;}核心參考代碼9、尋找最近點(diǎn)對給定平面上n個(gè)點(diǎn),找出其中的一對點(diǎn)的距離,使得在這n個(gè)點(diǎn)的所有點(diǎn)對中,該距離為所有點(diǎn)對中最小的。（n<=60000）分析【問題簡述】給定平面上n個(gè)點(diǎn)的坐標(biāo)，找出其中歐幾里德距離最近的兩個(gè)點(diǎn)?！痉椒?】枚舉算法。需要枚舉O(n2)個(gè)點(diǎn)對，每個(gè)距離的計(jì)算時(shí)間為O(1)，故總的時(shí)間復(fù)雜度為O(n2)。有沒有更好的算法呢？【方法2】分治算法

先按照X坐標(biāo)排序，把所有點(diǎn)劃分成個(gè)數(shù)盡量相等的兩部分，分別求最近點(diǎn)對，設(shè)距離分別為dL和dr。合并：令d=min{dL,dr}，則跨越兩邊的點(diǎn)對中，只有下面的豎條中的才有可能更近。需要檢查豎條里的所有點(diǎn)對嗎？由d的意義可知，P2中任何2個(gè)S中的點(diǎn)的距離都不小于d。由此而來可以推出矩形R中最多只有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<d。這與d的意義相矛盾。也就是說矩形R中最多只有6個(gè)S中的點(diǎn)。由于這種稀疏性質(zhì)，對于P1中任一點(diǎn)p，P2中最多只有6個(gè)點(diǎn)與它構(gòu)成最接近點(diǎn)對的候選者。第五部分貪心策略序言近年來的信息學(xué)競賽中，經(jīng)常需要求一個(gè)問題的可行解和最優(yōu)解，這就是所謂的最優(yōu)化問題。貪心法是求解這類問題的一種常用算法。在眾多的算法中，貪心法可以算得上是最接近人們?nèi)粘Ｋ季S的一種算法，它在各級各類信息學(xué)競賽、尤其在一些數(shù)據(jù)規(guī)模很大的問題中發(fā)揮著越來越重要的作用。一、什么是貪心法貪心法是從問題的某一個(gè)初始狀態(tài)出發(fā)，通過逐步構(gòu)造最優(yōu)解的方法向給定的目標(biāo)前進(jìn)，并期望通過這種方法產(chǎn)生出一個(gè)全局最優(yōu)解的方法。貪心方法的基本思想貪心是一種解題策略，也是一種解題思想使用貪心方法需要注意局部最優(yōu)與全局最優(yōu)的關(guān)系，選擇當(dāng)前狀態(tài)的局部最優(yōu)并不一定能推導(dǎo)出問題的全局最優(yōu)利用貪心策略解題，需要解決兩個(gè)問題：該題是否適合于用貪心策略求解如何選擇貪心標(biāo)準(zhǔn)，以得到問題的最優(yōu)解

【引例】在一個(gè)N×M的方格陣中，每一格子賦予一個(gè)數(shù)（即為權(quán)），規(guī)定每次移動時(shí)只能向上或向右?，F(xiàn)試找出一條路徑，使其從左下角至右上角所經(jīng)過的權(quán)之和最大。我們以2×3的矩陣為例：若按貪心策略求解，所得路徑為：1→3→4→6；若按動態(tài)規(guī)劃求解，所得路徑為：1→2→10→6。適用于貪心策略求解的問題的特點(diǎn)適用于貪心策略求解的問題必須具有最優(yōu)子結(jié)構(gòu)的性質(zhì)，但并不是所有具有最優(yōu)子結(jié)構(gòu)的問題都可以用貪心策略求解。因?yàn)樨澬耐敲つ康?，需要使用更理性的方法——動態(tài)規(guī)劃（例如“0-1背包問題”與“部分背包問題”）【問題1】部分背包問題給定一個(gè)最大載重量為M的卡車和N種食品，有食鹽，白糖，大米等。已知第i種食品的最多擁有Wi公斤，其商品價(jià)值為Vi元/公斤，編程確定一個(gè)裝貨方案，使得裝入卡車中的所有物品總價(jià)值最大?！痉治觥恳?yàn)槊恳粋€(gè)物品都可以分割成單位塊，單位塊的利益越大，顯然總收益越大，所以它局部最優(yōu)滿足全局最優(yōu)，可以用貪心法解答。方法如下：先將單位塊收益按從大到小進(jìn)行排列，然后用循環(huán)從單位塊收益最大的取起，直到不能取為止便得到了最優(yōu)解?！締栴}2】0/1背包問題給定一個(gè)最大載重量為M的卡車和N種動物。已知第i種動物的重量為Wi，其最大價(jià)值為Vi，設(shè)定M，Wi，Vi均為整數(shù)，編程確定一個(gè)裝貨方案，使得裝入卡車中的所有動物總價(jià)值最大?！痉治觥堪簇澬姆ǎ蟹蠢涸O(shè)N=3,卡車最大載重量是100,三種動物A、B、C的重量分別是40,50,70,其對應(yīng)的總價(jià)值分別是80、100、150。貪心策略與其他算法的區(qū)別

1.貪心與遞推：與遞推不同的是，貪心法中推進(jìn)的每一步不是依據(jù)某一固定的遞推式，而是當(dāng)前看似最佳的貪心決策，不斷的將問題歸納為更加小的相似的子問題。所以歸納、分析、選擇正確合適的貪心策略，是正確解決貪心問題的關(guān)鍵。

2.貪心與動態(tài)規(guī)劃：與動態(tài)規(guī)劃不同的是，貪心是鼠目寸光；動態(tài)規(guī)劃是統(tǒng)攬全局。幾個(gè)簡單的貪心例子

貪心策略例題1：刪數(shù)問題鍵盤輸入一個(gè)高精度的正整數(shù)n（n<=240位）,去掉其中任意s個(gè)數(shù)字后剩下的數(shù)字按照原來的次序?qū)⒔M成一個(gè)新的正整數(shù)。編程對給定的n和s,尋求一種方案,使得剩下組成的新數(shù)最小?！緲永斎搿?785434【樣例輸出】13

分析由于正整數(shù)n的有效位數(shù)最大可達(dá)240位，所以可以采用字符串類型來存儲n。那么，應(yīng)如何來確定該刪除哪s位呢？是不是只要刪掉最大的s個(gè)數(shù)字就可以了呢？為了盡可能地逼近目標(biāo)，我們選取的貪心策略為：每一步總是選擇一個(gè)使剩下的數(shù)最小的數(shù)字刪去，即按高位到低位的順序搜索，若各位數(shù)字遞增，則刪除最后一個(gè)數(shù)字，否則刪除第一個(gè)遞減區(qū)間的首字符。然后回到串首，按上述規(guī)則再刪除下一個(gè)數(shù)字。重復(fù)以上過程s次，剩下的數(shù)字串便是問題的解了。例題2：排隊(duì)問題

在一個(gè)食堂，有n個(gè)人排隊(duì)買飯，每個(gè)人買飯需要的時(shí)間為Ti，請你找出一種排列次序，是每個(gè)人買飯的時(shí)間總和最小?！舅悸伏c(diǎn)撥】由題意可知，本題可以采用的貪心策略為：將n個(gè)人排隊(duì)買飯的時(shí)間從小到大排序，再依次累加每人的買飯時(shí)間，即可得到最小的總和。由樣例可知，排好序后的數(shù)據(jù)為(1,3,5,7,9,11)，每個(gè)人的買飯時(shí)間如下：

T1=1T2=T1+T2=1+3=4T3=T2+T3=1+3+5=9T4=T3+t4=1+3+5+7=16T5=T4+T5=1+3+5+7+9=25T6=T5+T6=1+3+5+7+9+11=36

總時(shí)間T=T1+T2+T3+T4+T5+T6=91

用反證法證明如下：假設(shè)一個(gè)不排好序的n個(gè)人也能得到最優(yōu)答案，比如把(1,3,5,7,9,11)中的3,5對調(diào)一下，得到的序列為(1,5,3,7,9,11)。對調(diào)后，3,5前后的1,7,9,11四個(gè)人的買飯時(shí)間不會有變化，關(guān)鍵的變化是3,5兩個(gè)人。這時(shí)，5這個(gè)人的買飯時(shí)間為1+5，3這個(gè)人的買飯時(shí)間變?yōu)?+5+3，此時(shí)兩個(gè)人的總買飯時(shí)間中，5被累加了2次，而原方案中是3被累加了2次，其他一樣。由此，兩者相比較，可知有序的序列能得到最優(yōu)的方案。對于其他位置的改變可以采用同樣的方法證明。用反證法證明時(shí)，關(guān)鍵是證明反例不成立，由此推出原方案是最優(yōu)的。問題推廣：排隊(duì)打水問題有n個(gè)人排隊(duì)到r個(gè)水龍頭去打水，他們裝滿水桶的時(shí)間t1、t2…….tn為整數(shù)且各不相等，應(yīng)如何安排他們的打水順序才能使他們總共花費(fèi)的時(shí)間最少？【例題3】打包

某工廠生產(chǎn)出的產(chǎn)品都要被打包放入正四棱柱的盒子內(nèi)，所有盒子的高度為h，但地面尺寸不同，可以為1x1、2x2、3x3、4x4