第6章-貪心算法課件

第六章貪心算法若在求解一個(gè)問題時(shí)，能根據(jù)每次所得到的局部最優(yōu)解，推導(dǎo)出全局最優(yōu)或最優(yōu)目標(biāo)。那么，我們可以根據(jù)這個(gè)策略，每次得到局部最優(yōu)解答，逐步而推導(dǎo)出問題，這種策略稱為貪心法。下面我們看一些簡單例題?！纠?】在N行M列的正整數(shù)矩陣中，要求從每行中選出1個(gè)數(shù)，使得選出的總共N個(gè)數(shù)的和最大?！舅惴ǚ治觥?/p>

要使總和最大，則每個(gè)數(shù)要盡可能大，自然應(yīng)該選每行中最大的那個(gè)數(shù)。因此，我們?cè)O(shè)計(jì)出如下算法:讀入N,M,矩陣數(shù)據(jù)；Total:=0;ForI:=1toNdobegin //對(duì)N行進(jìn)行選擇選擇第I行最大的數(shù),記為K；

Total:=Total+K；End；輸出最大總和Total；從上例中我們可以看出，和遞推法相仿，貪心法也是從問題的某一個(gè)初始解出發(fā)，向給定的目標(biāo)遞推。但不同的是，推進(jìn)的每一步不是依據(jù)某一固定的遞推式，而是做一個(gè)局部的最優(yōu)選擇，即貪心選擇（在例中，這種貪心選擇表現(xiàn)為選擇一行中的最大整數(shù)），這樣，不斷的將問題歸納為若干相似的子問題，最終產(chǎn)生出一個(gè)全局最優(yōu)解。特別注意的是，局部貪心的選擇是否可以得出全局最優(yōu)是能否采用貪心法的關(guān)鍵所在。對(duì)于能否使用貪心策略，應(yīng)從理論上予以證明。下面我們看看另一個(gè)問題?！纠?】部分背包問題給定一個(gè)最大載重量為M的卡車和N種食品，有食鹽，白糖，大米等。已知第i種食品的最多擁有Wi公斤，其商品價(jià)值為Vi元/公斤，編程確定一個(gè)裝貨方案，使得裝入卡車中的所有物品總價(jià)值最大?！舅惴ǚ治觥?/p>

因?yàn)槊恳粋€(gè)物品都可以分割成單位塊，單位塊的利益越大顯然總收益越大，所以它局部最優(yōu)滿足全局最優(yōu)，可以用貪心法解答，方法如下：先將單位塊收益按從大到小進(jìn)行排列，然后用循環(huán)從單位塊收益最大的取起，直到不能取為止便得到了最優(yōu)解。因此我們非常容易設(shè)計(jì)出如下算法：問題初始化； //讀入數(shù)據(jù)按Vi從大到小將商品排序；I:=1;repeatifM=0thenBreak; //如果卡車滿載則跳出循環(huán)

M:=M-Wi;ifM>=0then將第I種商品全部裝入卡車

else

將(M+Wi)重量的物品I裝入卡車;I:=I+1; //選擇下一種商品until(M<=0)OR(I>N)

在解決上述問題的過程中，首先根據(jù)題設(shè)條件，找到了貪心選擇標(biāo)準(zhǔn)(Vi)，并依據(jù)這個(gè)標(biāo)準(zhǔn)直接逐步去求最優(yōu)解，這種解題策略被稱為貪心法。Nm10Wivi54224334因此，利用貪心策略解題，需要解決兩個(gè)問題：首先，確定問題是否能用貪心策略求解；一般來說，適用于貪心策略求解的問題具有以下特點(diǎn)：

①可通過局部的貪心選擇來達(dá)到問題的全局最優(yōu)解。運(yùn)用貪心策略解題，一般來說需要一步步的進(jìn)行多次的貪心選擇。在經(jīng)過一次貪心選擇之后，原問題將變成一個(gè)相似的，但規(guī)模更小的問題，而后的每一步都是當(dāng)前看似最佳的選擇，且每一個(gè)選擇都僅做一次。

②原問題的最優(yōu)解包含子問題的最優(yōu)解，即問題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)。在背包問題中，第一次選擇單位重量價(jià)值最大的貨物，它是第一個(gè)子問題的最優(yōu)解，第二次選擇剩下的貨物中單位重量價(jià)值最大的貨物，同樣是第二個(gè)子問題的最優(yōu)解，依次類推。

③其次，如何選擇一個(gè)貪心標(biāo)準(zhǔn)？正確的貪心標(biāo)準(zhǔn)可以得到問題的最優(yōu)解，在確定采用貪心策略解決問題時(shí)，不能隨意的判斷貪心標(biāo)準(zhǔn)是否正確，尤其不要被表面上看似正確的貪心標(biāo)準(zhǔn)所迷惑。在得出貪心標(biāo)準(zhǔn)之后應(yīng)給予嚴(yán)格的數(shù)學(xué)證明。下面來看看0-1背包問題。給定一個(gè)最大載重量為M的卡車和N種動(dòng)物。已知第i種動(dòng)物的重量為Wi，其最大價(jià)值為Vi，設(shè)定M，Wi，Vi均為整數(shù)，編程確定一個(gè)裝貨方案，使得裝入卡車中的所有動(dòng)物總價(jià)值最大?！痉治觥繉?duì)于N種動(dòng)物，要么被裝，要么不裝，也就是說在滿足卡車載重的條件下，如何選擇動(dòng)物，使得動(dòng)物價(jià)值最大的問題。即確定一組X1，X2，…，Xn，Xi∈{0,1}

f(x)=max(∑Xi*Vi)其中，∑(Xi*Wi)≦W

從直觀上來看，我們可以按照上例一樣選擇那些價(jià)值大，而重量輕的動(dòng)物。也就是可以按價(jià)值質(zhì)量比（Vi/Wi）的大小來進(jìn)行選擇。可以看出，每做一次選擇，都是從剩下的動(dòng)物中選擇那些Vi/Wi最大的，這種局部最優(yōu)的選擇是否能滿足全局最優(yōu)呢？我們來看看一個(gè)簡單的例子：設(shè)N=3，卡車最大載重量是100，三種動(dòng)物A、B、C的重量分別是40，50，70，其對(duì)應(yīng)的總價(jià)值分別是80、100、150。情況A：按照上述思路，三種動(dòng)物的Vi/Wi分別為2,2,2.14。顯然，我們首先選擇動(dòng)物C，得到價(jià)值150，然后任意選擇A或B，由于卡車最大載重為100，因此卡車不能裝載其他動(dòng)物。情況B：不按上述約束條件，直接選擇A和B?？梢缘玫絻r(jià)值80+100=180，卡車裝載的重量為40+50=90。沒有超過卡車的實(shí)際載重，因此也是一種可行解，顯然，這種解比上一種解要優(yōu)化。問題出現(xiàn)在什么地方呢？我們看看圖23從圖23中明顯可以看出，情況A，卡車的空載率比情況B高。也就是說，上面的分析，只考慮了貨物的價(jià)值質(zhì)量比，而沒有考慮到卡車的運(yùn)營效率，因此，局部的最優(yōu)化，不能導(dǎo)致全局的最優(yōu)化。因此，貪心不能簡單進(jìn)行，而需要全面的考慮，最后得到證明?！纠?】排隊(duì)打水問題有N個(gè)人排隊(duì)到R個(gè)水龍頭去打水，他們裝滿水桶的時(shí)間為T1，T2，…，Tn為整數(shù)且各不相等，應(yīng)如何安排他們的打水順序才能使他們花費(fèi)的總時(shí)間最少？【算法分析】

由于排隊(duì)時(shí)，越靠前面的計(jì)算的次數(shù)越多，顯然越小的排在越前面得出的結(jié)果越小（可以用數(shù)學(xué)方法簡單證明，這里就不再贅述），所以這道題可以用貪心法解答，基本步驟：(1)將輸入的時(shí)間按從小到大排序；(2)將排序后的時(shí)間按順序依次放入每個(gè)水龍頭的隊(duì)列中；(3)統(tǒng)計(jì)，輸出答案?！緲永斎搿?2//4人打水，2個(gè)水龍頭

2645//每個(gè)打水時(shí)間參考程序主要框架如下：

read(n,r);Fillchar(S,Sizeof(S),0);J:=0;Min:=0;ForI:=1ToNDo//用貪心法求解

Begin

Inc(J);IfJ=R+1ThenJ:=1;S[J]:=S[J]+A[I];Min:=Min+S[J];End;

Writeln(Min);//輸出解答【樣例輸出】23//總共花費(fèi)時(shí)間【例4】均分紙牌（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張牌放到①（1010

10

10）。【輸入格式】N（N堆紙牌，1<=N<=100）A1A2…An（N堆紙牌，每堆紙牌初始數(shù)，l<=Ai<=10000）【輸出格式】所有堆均達(dá)到相等時(shí)的最少移動(dòng)次數(shù)?！緲永斎搿?Playcard.in)

4

98176【樣例輸出】(Playcard.out)

3【算法分析】

如果你想到把每堆牌的張數(shù)減去平均張數(shù)，題目就變成移動(dòng)正數(shù)，加到負(fù)數(shù)中，使大家都變成0，那就意味著成功了一半！拿例題來說，平均張數(shù)為10,原張數(shù)9，8，17，6，變?yōu)?1，-2，7，-4，其中沒有為0的數(shù)，我們從左邊出發(fā)：要使第1堆的牌數(shù)-1變?yōu)?，只須將-1張牌移到它的右邊（第2堆）-2中；結(jié)果是-1變?yōu)?，-2變?yōu)?3，各堆牌張數(shù)變?yōu)?，-3，7，-4；同理：要使第2堆變?yōu)?，只需將-3移到它的右邊（第3堆）中去，各堆牌張數(shù)變?yōu)?，0，4，-4；要使第3堆變?yōu)?，只需將第3堆中的4移到它的右邊（第4堆）中去，結(jié)果為0，0，0，0，完成任務(wù)。每移動(dòng)1次牌，步數(shù)加1。也許你要問，負(fù)數(shù)張牌怎么移，不違反題意嗎？其實(shí)從第i堆移動(dòng)-m張牌到第i+1堆，等價(jià)于從第i+1堆移動(dòng)m張牌到第i堆，步數(shù)是一樣的。如果張數(shù)中本來就有為0的，怎么辦呢？如0，-1，-5，6，還是從左算起（從右算起也完全一樣），第1堆是0，無需移牌，余下與上相同；再比如-1，-2，3，10，-4，-6，從左算起，第1次移動(dòng)的結(jié)果為0，-3，3，10，-4，-6；第2次移動(dòng)的結(jié)果為0，0，0，10，-4，-6，現(xiàn)在第3堆已經(jīng)變?yōu)?了，可節(jié)省1步，余下繼續(xù)。參考程序主要框架如下：

ave:=0;step:=0;fori:=1tondobegin

read(a[i]);inc(ave,a[i]);//讀入各堆牌張數(shù)，求總張數(shù)ave

end;

ave:=avedivn;//求牌的平均張數(shù)ave

fori:=1tondoa[i]:=a[i]-ave;//每堆牌的張數(shù)減去平均數(shù)

i:=1;j:=n;while(a[i]=0)and(i<n)doinc(i);//過濾左邊的0while(a[j]=0)and(j>1)dodec(j);//過濾右邊的0while(i<j)dobegininc(a[i+1],a[i]);//將第i堆牌移到第i+1堆中去

a[i]:=0;//第i堆牌移走后變?yōu)?

inc(step);//移牌步數(shù)計(jì)數(shù)

inc(i);//對(duì)下一堆牌進(jìn)行循環(huán)操作

while(a[i]=0)and(i<j)doinc(i);//過濾移牌過程中產(chǎn)生的0end;

writeln(step);

點(diǎn)評(píng)：基本題（較易）本題有3點(diǎn)比較關(guān)鍵：一是善于將每堆牌數(shù)減去平均數(shù)，簡化了問題；二是要過濾掉0（不是所有的0，如-2，3，0，-1中的0是不能過濾的）；三是負(fù)數(shù)張牌也可以移動(dòng)，這是辯證法（關(guān)鍵中的關(guān)鍵）?！纠?】刪數(shù)問題（NOI94）輸入一個(gè)高精度的正整數(shù)N，去掉其中任意S個(gè)數(shù)字后剩下的數(shù)字按原左右次序組成一個(gè)新的正整數(shù)。編程對(duì)給定的N和S，尋找一種方案使得剩下的數(shù)字組成的新數(shù)最小。輸出應(yīng)新的正整數(shù)。（N不超過240位）輸入數(shù)據(jù)均不需判錯(cuò)?！据斎搿縩s【輸出】最后剩下的最小數(shù)?！緲永斎搿?754384【樣例輸出】13【算法分析】

由于正整數(shù)n的有效數(shù)位為240位，所以很自然地采用字符串類型存貯n。那么如何決定哪s位被刪除呢？是不是最大的s個(gè)數(shù)字呢？顯然不是，大家很容易舉出一些反例。為了盡可能逼近目標(biāo)，我們選取的貪心策略為：每一步總是選擇一個(gè)使剩下的數(shù)最小的數(shù)字刪去，即按高位到低位的順序搜索，若各位數(shù)字遞增，則刪除最后一個(gè)數(shù)字；否則刪除第一個(gè)遞減區(qū)間的首字符，這樣刪一位便形成了一個(gè)新數(shù)字串。然后回到串首，按上述規(guī)則再刪下一個(gè)數(shù)字。重復(fù)以上過程s次為止，剩下的數(shù)字串便是問題的解了。例如：n=175438s=4

刪數(shù)的過程如下：

n=175438//刪掉715438//刪掉51438//刪掉4138//刪掉813//解為13

這樣，刪數(shù)問題就與如何尋找遞減區(qū)間首字符這樣一個(gè)簡單的問題對(duì)應(yīng)起來。不過還要注意一個(gè)細(xì)節(jié)性的問題，就是可能會(huì)出現(xiàn)字符串串首有若干0的情況，甚至整個(gè)字符串都是0的情況。按以上貪心策略編制的程序框架如下輸入n，s；

whiles>0dobegini：=1；//從串首開始找

while(i<length(n))and(n[i]<=n[i+1])doi:=i+1；

delete(n，i，1)；//刪除字符串n的第i個(gè)字符

s:=s-1；

end；

while(length(n)>1)and(n[1]=‘0’)dodelete(n，1，1)；輸出n；//刪去串首可能產(chǎn)生的無用零【例6】攔截導(dǎo)彈問題（NOIP1999）某國為了防御敵國的導(dǎo)彈襲擊，開發(fā)出一種導(dǎo)彈攔截系統(tǒng)，但是這種攔截系統(tǒng)有一個(gè)缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國的導(dǎo)彈來襲，由于該系統(tǒng)還在試用階段。所以一套系統(tǒng)有可能不能攔截所有的導(dǎo)彈。輸入導(dǎo)彈依次飛來的高度（雷達(dá)給出的高度不大于30000的正整數(shù)）。計(jì)算要攔截所有導(dǎo)彈最小需要配備多少套這種導(dǎo)彈攔截系統(tǒng)?！据斎敫袷健縩顆依次飛來的高度（1≤n≤1000）.【輸出格式】要攔截所有導(dǎo)彈最小配備的系統(tǒng)數(shù)k?！据斎霕永縨issile.in38920715530029917015865【輸出樣例】missile.out2【輸入輸出樣例】輸入：導(dǎo)彈高度：79685輸出：導(dǎo)彈攔截系統(tǒng)K=2輸入：導(dǎo)彈高度：432輸出：導(dǎo)彈攔截系統(tǒng)K=1【算法分析】

按照題意，被一套系統(tǒng)攔截的所有導(dǎo)彈中，最后一枚導(dǎo)彈的高度最低。設(shè)：k為當(dāng)前配備的系統(tǒng)數(shù)；

L[k]為被第k套系統(tǒng)攔截的最后一枚導(dǎo)彈的高度，簡稱系統(tǒng)k的最低高度（1≤k≤n）。我們首先設(shè)導(dǎo)彈1被系統(tǒng)1所攔截（k←1,L[k]←導(dǎo)彈1的高度）。然后依次分析導(dǎo)彈2，…，導(dǎo)彈n的高度。若導(dǎo)彈i的高度高于所有系統(tǒng)的最低高度，則斷定導(dǎo)彈i不能被這些系統(tǒng)所攔截，應(yīng)增設(shè)一套系統(tǒng)來攔截導(dǎo)彈I(k←k+1,L[k]←導(dǎo)彈i的高度)；若導(dǎo)彈i低于某些系統(tǒng)的最低高度，那么導(dǎo)彈i均可被這些系統(tǒng)所攔截。究竟選擇哪個(gè)系統(tǒng)攔截可使得配備的系統(tǒng)數(shù)最少，我們不妨采用貪心策略，選擇其中最低高度最小（即導(dǎo)彈i的高度與系統(tǒng)最低高度最接近）的一套系統(tǒng)p(L[p]=min{L[j]|L[j]>導(dǎo)彈I的高度}；L[p]←導(dǎo)彈i的高度)（i≤j≤k）。這樣可使得一套系統(tǒng)攔截的導(dǎo)彈數(shù)盡可能增多。依次類推，直至分析了n枚導(dǎo)彈的高度為止。此時(shí)得出的k便為應(yīng)配備的最少系統(tǒng)數(shù)。參考程序主要框架如下：

k:=1;L[1]:=導(dǎo)彈1的高度;fori:=2tondobeginp:=0;forj:=1tokdoif(L[j]>=導(dǎo)彈i的高度)thenifp=0thenp:=jelseifL[j]<L[p]thenp:=j;ifp=0thenbegink:=k+1;L[k]:=導(dǎo)彈i的高度;endelseL[p]:=導(dǎo)彈i的高度;end;輸出應(yīng)配備的最少系統(tǒng)數(shù)K?！旧蠙C(jī)練習(xí)】1、刪數(shù)問題（NOI94）【問題描述】鍵盤輸入一個(gè)高精度的正整數(shù)n(≤240位)，去掉其中任意s個(gè)數(shù)字后剩下的數(shù)字按原左右次序?qū)⒔M成一個(gè)新的正整數(shù)。編程對(duì)給定的n和s，尋找一種方案，使得剩下的數(shù)字組成的新數(shù)最小?！据斎敫袷健縩s【輸出格式】最后剩下的最小數(shù)?！据斎霕永縟elete.in1754384【輸出樣例】delete.out132、均分紙牌（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張牌放到①（1010

10

10）?！据斎敫袷健縉（N堆紙牌，1<=N<=100）A1A2…An（N堆紙牌，每堆紙牌初始數(shù)，l<=Ai<=10000）【輸出格式】所有堆均達(dá)到相等時(shí)的最少移動(dòng)次數(shù)?！緲永斎搿?Playcard.in)

4

98176【樣例輸出】(Playcard.out)

33、攔截導(dǎo)彈問題（NOIP1999）【問題描述】某國為了防御敵國的導(dǎo)彈襲擊，開發(fā)出一種導(dǎo)彈攔截系統(tǒng)，但是這種攔截系統(tǒng)有一個(gè)缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國的導(dǎo)彈來襲，由于該系統(tǒng)還在試用階段。所以一套系統(tǒng)有可能不能攔截所有的導(dǎo)彈。輸入導(dǎo)彈依次飛來的高度（雷達(dá)給出的高度不大于30000的正整數(shù)）。計(jì)算要攔截所有導(dǎo)彈最小需要配備多少套這種導(dǎo)彈攔截系統(tǒng)。【輸入格式】n顆依次飛來的高度（1≤n≤1000）.【輸出格式】要攔截所有導(dǎo)彈最小配備的系統(tǒng)數(shù)k。【輸入樣例】missile.in38920715530029917015865【輸出樣例】missile.out24、排隊(duì)接水(water.pas)【問題描述】

有n個(gè)人在一個(gè)水龍頭前排隊(duì)接水，假如每個(gè)人接水的時(shí)間為Ti，請(qǐng)編程找出這n個(gè)人排隊(duì)的一種順序，使得n個(gè)人的平均等待時(shí)間最小?！据斎敫袷健?/p>

輸入文件共兩行，第一行為n；第二行分別表示第1個(gè)人到第n個(gè)人每人的接水時(shí)間T1，T2，…，Tn，每個(gè)數(shù)據(jù)之間有1個(gè)空格?！据敵龈袷健?/p>

輸出文件有兩行，第一行為一種排隊(duì)順序，即1到n的一種排列；第二行為這種排列方案下的平均等待時(shí)間(輸出結(jié)果精確到小數(shù)點(diǎn)后兩位)?！据斎胼敵鰳永?/p>

water.in

10 32781496105 56121991000234335599812 water.out532.005、最大整數(shù)（Noip1998連接多位數(shù)）【問題描述】

設(shè)有n個(gè)正整數(shù)（n≤20），將它們聯(lián)接成一排，組成一個(gè)最大的多位整數(shù)。例如：n=3時(shí)，3個(gè)整數(shù)13，312，343聯(lián)接成的最大整數(shù)為：34331213

又如：n=4時(shí)，4個(gè)整數(shù)7，13，4，246聯(lián)接成的最大整數(shù)為：7424613【輸入格式】nn個(gè)數(shù)【輸出格式】聯(lián)接成的多位數(shù)【輸入樣例】maxnum.in313312343【輸出樣例】maxnum.out34331213【輸入樣例】maxnum.in331312343【輸出樣例】maxnum.out343313126、紀(jì)念品分組(NOIP2007)【題目描述】

元旦快到了，校學(xué)生會(huì)讓樂樂負(fù)責(zé)新年晚會(huì)的紀(jì)念品發(fā)放工作。為使得參加晚會(huì)的同學(xué)所獲得的紀(jì)念品價(jià)值相對(duì)均衡，他要把購來的紀(jì)念品根據(jù)價(jià)格進(jìn)行分組，但每組最多只能包括兩件紀(jì)念品，并且每組紀(jì)念品的價(jià)格之和不能超過一個(gè)給定的整數(shù)。為了保證在盡量短的時(shí)間內(nèi)發(fā)完所有紀(jì)念品，樂樂希望分組的數(shù)目最少。你的任務(wù)是寫一個(gè)程序，找出所有分組方案中分組數(shù)最少的一種，輸出最少的分組數(shù)目。【輸入格式】

輸入文件group.in包含n+2行：第1行包括一個(gè)整數(shù)w，為每組紀(jì)念品價(jià)格之和的上限。第2行為一個(gè)整數(shù)n，表示購來的紀(jì)念品的總件數(shù)。第3~n+2行每行包含一個(gè)正整數(shù)pi(5<=pi<=w)，表示所對(duì)應(yīng)紀(jì)念品的價(jià)格?！据敵龈袷健?/p>

輸出文件group.out僅一行，包含一個(gè)整數(shù)，即最少的分組數(shù)目?！据斎胼敵鰳永俊鞠拗啤?0%的數(shù)據(jù)滿足：1<=n<=15100%的數(shù)據(jù)滿足：1<=n<=30000,80<=w<=200group.in1009902020305060708090group.out67、合并果子(Noip2004)【問題描述】

在一個(gè)果園里，多多已經(jīng)將所有的果子打了下來，而且按果子的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和?？梢钥闯?，所有的果子經(jīng)過n-1次合并之后，就只剩下一堆了。多多在合并果子時(shí)總共消耗的體力等于每次合并所耗體力之和。因?yàn)檫€要花大力氣把這些果子搬回家，所以多多在合并果子時(shí)要盡可能地節(jié)省體力。假定每個(gè)果子重量都為1，并且已知果子的種類數(shù)和每種果子的數(shù)目，你的任務(wù)是設(shè)計(jì)出合并的次序方案，使多多耗費(fèi)的體力最少，并輸出這個(gè)最小的體力耗費(fèi)值。例如有3種果子，數(shù)目依次為1，2，9?？梢韵葘?、2堆合并，新堆數(shù)目為3，耗費(fèi)體力為3。接著，將新堆與原先的第三堆合并，又得到新的堆，數(shù)目為12，耗費(fèi)體力為12。所以多多總共耗費(fèi)體力=3+12=15?？梢宰C明15為最小的體力耗費(fèi)值?！据斎胛募?/p>

輸入文件fruit.in包括兩行，第一行是一個(gè)整數(shù)n（1<=n<=10000），表示果子的種類數(shù)。第二行包含n個(gè)整數(shù)，用空格分隔，第i個(gè)整數(shù)ai（1<=ai<=20000）是第i種果子的數(shù)目?！据敵鑫募?/p>

輸出文件fruit.out包括一行，這一行只包含一個(gè)整數(shù)，也就是最小的體力耗費(fèi)值。輸入數(shù)據(jù)保證這個(gè)值小于231。【樣例輸入】3129【樣例輸出】15【數(shù)據(jù)規(guī)?！繉?duì)于30%的數(shù)據(jù)，保證有n<=1000；對(duì)于50%的數(shù)據(jù)，保證有n<=5000；對(duì)于全部的數(shù)據(jù)，保證有n<=10000。8、美元匯率（DOLLARS.PAS）【問題描述】

在以后的若干天里戴維將學(xué)習(xí)美元與德國馬克的匯率。編寫程序幫助戴維何時(shí)應(yīng)買或賣馬克或美元，使他從100美元開始，最后能獲得最高可能的價(jià)值?！据斎敫袷健?/p>

輸入文件的第一行是一個(gè)自然數(shù)N，1≤N≤100，表示戴維學(xué)習(xí)匯率的天數(shù)。接下來的N行中每行是一個(gè)自然數(shù)A，1≤A≤1000。第i+1行的A表示預(yù)先知道的第i+1天的平均匯率，在這一天中，戴維既能用100美元買A馬克也能用A馬克購買100美元?！据敵龈袷健?/p>

輸出文件的第一行也是唯一的一行應(yīng)輸出要求的錢數(shù)(單位為美元，保留兩位小數(shù))。注意：考慮到實(shí)數(shù)算術(shù)運(yùn)算中進(jìn)位的誤差，結(jié)果在正確結(jié)果0.05美元范圍內(nèi)的被認(rèn)為是正確的，戴維必須在最后一天結(jié)束之前將他的錢都換成美元?！据斎霕永緿OLLARS.IN5400300500300250【輸出樣例】DOLLARS.OUT266.66樣例解釋(無需輸出)Day1...changing100.0000美元=400.0000馬克Day2...changing400.0000馬克=133.3333美元Day3...changing133.3333美元=666.6666馬克Day5...changing666.6666馬克=266.6666美元9、零件分組（stick.pas）【問題描述】

某工廠生產(chǎn)一批棍狀零件，每個(gè)零件都有一定的長度（Li）和重量（Wi）?，F(xiàn)在為了加工需要，要將它們分成若干組，使每一組的零件都能排成一個(gè)長度和重量都不下降（若i<j，則Li<=Lj，Wi<=Wj）的序列。請(qǐng)問至少要分成幾組?【輸入格式】

第一行為一個(gè)整數(shù)N（N<=1000），表示零件的個(gè)數(shù)。第二行有N對(duì)正整數(shù)，每對(duì)正整數(shù)表示這些零件的長度和重量，長度和重量均不超過10000。【輸出格式】

僅一行，即最少分成的組數(shù)。【輸入樣例】STICK.IN58438239735【輸出樣例】STICK.OUT210、取數(shù)游戲（game.pas）【問題描述】給出2n（n<=100）個(gè)自然數(shù)（數(shù)小于等于30000）。游戲雙方分別為A方（計(jì)算機(jī)方）和B方（對(duì)弈的人）。只允許從數(shù)列兩頭取數(shù)。A先取，然后雙方依次輪流取數(shù)。取完時(shí)，誰取得的數(shù)字總和最大為取勝方。若雙方和相等，屬于A勝?，F(xiàn)告訴你A方有必勝的策略，請(qǐng)你求出A方必勝時(shí)A方所取各數(shù)的總和。

輸入文件game.in

：只有一行，1個(gè)整數(shù)N。輸出文件game.out

，只有一行，是一個(gè)整數(shù)，表示A方所取的各數(shù)總和。樣例輸入:479364253輸出:20設(shè)n=4，自然數(shù)列為7

9

3

6

4

2

5

3，我們?cè)O(shè)計(jì)一種原始的貪心策略，讓A每次取數(shù)列兩頭較大的那個(gè)數(shù)，則游戲者也不會(huì)傻，他也會(huì)這么干，所以在上面的數(shù)列中，A方會(huì)順序取7、3、4、5，B方會(huì)順序取9、6、2、3，由此得出：A方取得的數(shù)和為7+3+4+5=19，B方取得的數(shù)和為9+6+2+3=20，按照規(guī)則，判定A方輸。

其實(shí)，如果按上述貪心策略去游戲，成敗取決于給你的測(cè)試數(shù)據(jù)！不過，雖然A方敗給B方，但是我們卻發(fā)現(xiàn)了一個(gè)有趣的事實(shí)：A方取走偶位置的數(shù)后，剩下兩端數(shù)都處于奇位置；反之，若A方取走奇位置的數(shù)后，剩下兩端數(shù)都處于偶位置。即無論B方如何取法，A方即可以取走奇位置的所有數(shù)，亦可以取走偶位置的所有數(shù)。由此萌發(fā)出另一種有效的貪心策略：若能夠讓A方取走“數(shù)和較大的奇（或偶）位置上的所有數(shù)”，則A方必勝。這樣，取數(shù)問題便對(duì)應(yīng)于一個(gè)簡單問題：讓A方取奇偶位置中數(shù)和較大的一半數(shù)。設(shè)j為A取數(shù)的奇偶位置標(biāo)志，則j=0表示偶位置數(shù)和較大，A取偶位置上的所有數(shù)；j=1表示奇位置數(shù)和較大，A取奇位置的所有數(shù)。

設(shè)SA，SB分別表示A方取數(shù)和，B方取數(shù)和（SA≥SB）；a存儲(chǔ)2n個(gè)自然數(shù)序列；lp，rp為序列的左端位置和右端位置；ch為B方取數(shù)的位置信息（’L’或’R’）；按上述貪心思想編寫的程序框架如下：constmaxn=100;var

sa,sb:longint;

i,n:integer;a:array[1..2*maxn]ofinteger;beginreadln(n);fori:=1to2*ndoread(a[i]);SA:=0;SB:=0;{計(jì)算A方取數(shù)和、B方取數(shù)和}fori:=1tondobeginSA:=SA+a[2*i-1];SB:=SB+a[2*i];end;ifSA>=SBthenwriteln(SA)elsewriteln(SB);end.【樣例輸入】113514121481206811610573859213【樣例輸出】411、活動(dòng)選擇（act.pas）問題描述：

有一個(gè)需要使用每個(gè)資源的n個(gè)活動(dòng)組成的集合S=

{a1，a2，···，an

},資源每次只能由一個(gè)活動(dòng)使用。每個(gè)活動(dòng)a都有一個(gè)開始時(shí)間和結(jié)束時(shí)間，且

0<=

s

<

f

<∞

。一旦被選擇后，活動(dòng)a就占據(jù)半開時(shí)間區(qū)間[s,f]。如果[s,f]和[s,f]互不重疊，則稱兩個(gè)活動(dòng)是兼容的。該問題就是要找出一個(gè)由互相兼容的活動(dòng)組成的最大子集。輸入：act.in，共n+1行，其中第一行為n，第2行到第n+1行表示n個(gè)活動(dòng)飛開始時(shí)間和結(jié)束時(shí)間。輸出：act.out，共1行，最大的子集數(shù)。解析：1、按結(jié)束時(shí)間遞增排序；2、每次總是選擇具有最早完成時(shí)間的相容活動(dòng)加入集合A中。直觀上，按這種方法選擇相容活動(dòng)為未安排活動(dòng)留下盡可能多的時(shí)間。也就是說，該算法的貪心選擇的意義是使剩余的可安排時(shí)間段極大化，以便安排盡可能多的相容活動(dòng)。var

aa:array[1..100,1..2]oflongint;

a,b,c,d,e:longint;

begin

read(a);

forb:=1toado

readln(aa[b,1],aa[b,2]);

writeln;

forb:=1toado

forc:=1toa-1do

ifaa[b,2]<aa[c,2]then

begin

d:=aa[b,1];

aa[b,1]:=aa[c,1];

aa[c,1]:=d;

d:=aa[b,2];

aa[b,2]:=aa[c,2];

aa[c,2]:=d;

end;

c:=1;

d:=1;

whiletruedo

begin

forb:=1toado

Ifaa[b,1]>aa[c,2]then

begin

c:=b;

d:=d+1;

break;

end;

forb:=1toado

ifaa[b,1]<aa[c,2]thene:=e+1;

ife=athenbegin

writeln(d);

halt;

end

elsee:=0;

end;

end.12.最后一章之馬拉松某城市冬季舉辦環(huán)城25km馬拉松接力賽，每個(gè)代表隊(duì)有5人參加比賽，比賽要求每個(gè)城市的每名參賽選手只能跑一次，一次至少跑1km、最多只能跑10km，而且每個(gè)選手所跑的公里數(shù)必須為整數(shù)，即接力的地方在整公里處。

劉老師作為學(xué)校代表隊(duì)的教練，精心選擇了5名長跑能手，進(jìn)行了訓(xùn)練和測(cè)試，得到了這5名選手盡力連續(xù)跑1km、2km、…、10km的所用時(shí)間?，F(xiàn)在他要進(jìn)行一個(gè)合理的安排，讓每個(gè)選手跑合適的公里數(shù)，使學(xué)校代表隊(duì)跑完25km所用的時(shí)間最短。根據(jù)隊(duì)員的情況，這個(gè)最短的時(shí)間是惟一的，但安排方案可能并不惟一。根據(jù)測(cè)試情況及一般運(yùn)動(dòng)員的情況得知，連續(xù)跑1km要比連續(xù)跑2km速度快，連續(xù)跑2km又要比連續(xù)跑3km速度快……也就是說連續(xù)跑的路程越長，速度越慢，當(dāng)然也有特殊的，就是速度不會(huì)變慢，但是絕不可能變快。【輸入】5行數(shù)據(jù)，分別是1到5號(hào)隊(duì)員的測(cè)試數(shù)據(jù)，每行的10個(gè)整數(shù)，表示某一個(gè)運(yùn)動(dòng)員盡力連續(xù)跑1km、2km、…、10km所用的時(shí)間?！据敵觥績尚?，第一行是最短的時(shí)間，第二行是五個(gè)數(shù)據(jù)，分別是1到5號(hào)隊(duì)員各自連續(xù)跑的公里數(shù)?！緲永枯斎耄?33700120017102240261332453956477858993006109601370180027123834483459987682298612990156021092896379047475996765428957789013811976273438765678689098763126339951467184526343636481259998123輸出：9748var

p:array[0..5,0..12]oflongint;

mi,m:array[0..5]oflongint;

i,j,a,b,c,z,g,a1,a2,a3,a4,a5:longint;

functionmin(a1,a2,a3,a4,a5:longint):longint;

begin

if(a1<=a2)and(a1<=a3)and(a1<=a4)and(a1<=a4)thenexit(1);

if(a2<=a1)and(a2<=a3)and(a2<=a4)and(a2<=a5)thenexit(2);

if(a3<=a1)and(a3<=a2)and(a3<=a4)and(a3<=a5)thenexit(3);

if(a4<=a1)and(a4<=a2)and(a4<=a3)and(a4<=a5)thenexit(4);

if(a5<=a1)and(a5<=a2)and(a5<=a3)and(a5<=a4)thenexit(5);

end;

begin

fori:=1to5do

begin

forj:=1to10do

read(p[i,j]);

readln;

end;fori:=1to5do

forj:=10downto1do

p[i,j]:=p[i,j]-p[i,j-1];

fori:=1to5do

p[i,11]:=maxlongintdiv2;

fori:=1to5do

begin

mi[i]:=1;

m[i]:=p[i,1];

z:=z+p[i,1];

end;

g:=5;

repeat

a:=min(p[1,mi[1]+1],p[2,mi[2]+1],p[3,mi[3]+1],p[4,mi[4]+1],p[5,mi[5]+1]);

g:=g+1;

mi[a]:=mi[a]+1;

m[a]:=m[a]+p[a,mi[a]];

z:=z+p[a,mi[a]];

untilg=25;

writeln(z);

end.13.旅行家的預(yù)算[問題描述]：一個(gè)旅行家想駕駛汽車以最少的費(fèi)用從一個(gè)城市到另一個(gè)城市（假設(shè)出發(fā)時(shí)油箱時(shí)空的）。給定兩個(gè)城市之間的距離D1、汽車油箱的容量C（以升為單位）、每升汽油能行駛的距離D2、出發(fā)點(diǎn)每升汽油價(jià)格P和沿途加油站數(shù)N（N可以為零），油站i離出發(fā)點(diǎn)的距離Di、每升汽油價(jià)格Pi（i=1，2，……，N）。計(jì)算結(jié)果四舍五入至小數(shù)點(diǎn)后兩位。輸入:第一行有5個(gè)數(shù)：D1，c，D2，P，N(前四個(gè)為實(shí)數(shù)，N為整數(shù),N<=1000)后面有N行，每行兩個(gè)實(shí)數(shù)，分別表示對(duì)應(yīng)的加油站離出發(fā)點(diǎn)的距離，與每升汽油的價(jià)格輸出:僅一行，即最少花費(fèi)

[樣例輸入]275.611.927.42.82102.02.9220.02.2[樣例輸出]26.95var

v,o,w,x:array[0..999]ofreal;

l,c,d,p,a:real;

i,j,n:integer;

begin

readln(l,c,d,p,n);

fori:=1tondo

readln(w[i],v[i]);

fori:=0tondo

begin

o[i]:=0;

x[i]:=0;

end;

n:=n+1;

w[n]:=1;

v[n]:=0;

i:=0;

l:=c*d;

v[0]:=p;

w[0]:=0;

o[0]:=0;

whilei<>ndo

begin

j:=i+1;

ifw[j]-w[i]>1then

begin

writeln('no');

halt;

end;

whilew[j]-w[i]<=1d