4、方便,我們把這兩種情況統(tǒng)一看作是將a[I]-v張牌從第I堆移動(dòng)到第I+1堆;移動(dòng)后有:a[I]:=v;a[I+1]:=a[I+1]+a[I]-v;在從第i+1堆中取出紙牌補(bǔ)充第i堆的過(guò)程中,可能會(huì)出現(xiàn)第i+1堆的紙牌數(shù)小于零(a[i+1]+a[i]-v<0)的情況。如n=3,三堆紙牌數(shù)為(1,2,27)這時(shí)v=10,為了使第一堆數(shù)為10,要從第二堆移9張紙牌到第一堆,而第二堆只有2張紙牌可移,這是不是意味著剛才使用的貪心法是錯(cuò)誤的呢?我們繼續(xù)按規(guī)則分析移牌過(guò)程,從第二堆移出9張到第一堆后,第一堆有10張紙牌,第二堆剩下-7張紙
5、牌,再?gòu)牡谌岩苿?dòng)17張到第二堆,剛好三堆紙牌數(shù)都是10,最后結(jié)果是對(duì)的,從第二堆移出的牌都可以從第三堆得到。我們?cè)谝苿?dòng)過(guò)程中,只是改變了移動(dòng)的順序,而移動(dòng)的次數(shù)不變,因此此題使用貪心法是可行的。源程序:vari,n,s:integer;v:longint;?a:array[1..100]oflongint;?f:text;fil:string;begin?readln(fil);assign(f,fil);reset(f);?readln(f,n);v:=0;?fori:=1tondobegin???read(f,a[i])
6、;inc(v,a[i]);?end;?v:=vdivn;{每堆牌的平均數(shù)}?fori:=1ton-1doifa[i]<>vthen{貪心選擇}begin?????inc(s);{移牌步數(shù)計(jì)數(shù)}?????a[i+1]:=a[i+1]+a[i]-v;{使第i堆牌數(shù)為v}???end;{then}?writeln(s);end.利用貪心算法解題,需要解決兩個(gè)問(wèn)題:一是問(wèn)題是否適合用貪心法求解。我們看一個(gè)找?guī)诺睦?如果一個(gè)貨幣系統(tǒng)有3種幣值,面值分別為一角、五分和一分,求最小找?guī)艛?shù)時(shí),可以用貪心法求解;如果將這三種幣值改為一角一分、
7、五分和一分,就不能使用貪心法求解。用貪心法解題很方便,但它的適用范圍很小,判斷一個(gè)問(wèn)題是否適合用貪心法求解,目前還沒(méi)有一個(gè)通用的方法,在信息學(xué)競(jìng)賽中,需要憑個(gè)人的經(jīng)驗(yàn)來(lái)判斷何時(shí)該使用貪心算法。二是確定了可以用貪心算法之后,如何選擇一個(gè)貪心標(biāo)準(zhǔn),才能保證得到問(wèn)題的最優(yōu)解。在選擇貪心標(biāo)準(zhǔn)時(shí),我們要對(duì)所選的貪心標(biāo)準(zhǔn)進(jìn)行驗(yàn)證才能使用,不要被表面上看似正確的貪心標(biāo)準(zhǔn)所迷惑,如下面的列子。例2(NOIP1998tg)設(shè)有n個(gè)正整數(shù),將他們連接成一排,組成一個(gè)最大的多位整數(shù)。例如:n=3時(shí),3個(gè)整數(shù)13,312,343,連成的最大整數(shù)為:3
8、4331213又如:n=4時(shí),4個(gè)整數(shù)7,13,4,246連接成的最大整數(shù)為7424613輸入:NN個(gè)數(shù)輸出:連接成的多位數(shù)算法分析:此題很容易想到使用貪心法,在考試時(shí)有很多同學(xué)把整數(shù)按從大到小的順序連接起來(lái),測(cè)試題目的例子也都符合,但最后測(cè)試的結(jié)果卻不全對(duì)。按這種貪心標(biāo)準(zhǔn),