1貪心法習(xí)題匯總我們發(fā)現(xiàn)上述△total恒大于0，所以也說(shuō)明了任何次序的改變，都會(huì)導(dǎo)致等待時(shí)間的增加。從而證明了我們的設(shè)想。既然如此，我們就得到了一種最有貪心策略：把接水時(shí)間少的人盡可能排在前面。這樣一樣，問(wèn)題的本質(zhì)就變成：把n個(gè)等待時(shí)間按非遞減順序排列，輸出這種排列，并求出這種排列下的平均等待時(shí)間。17/17
2貪心法習(xí)題匯總3.2智力大沖浪源程序名riddle.???（pas,c,cpp）可執(zhí)行文件名riddle.exe輸入文件名riddle.in輸出文件名riddle.out【問(wèn)題描述】小偉報(bào)名參加中央電視臺(tái)的智力大沖浪節(jié)目。本次挑戰(zhàn)賽吸引了眾多參賽者，主持人為了表彰大家的勇氣，先獎(jiǎng)勵(lì)每個(gè)參賽者m元。先不要太高興！因?yàn)檫@些錢還不一定都是你的？！接下來(lái)主持人宣布了比賽規(guī)則：首先，比賽時(shí)間分為n個(gè)時(shí)段(n≤500)，它又給出了很多小游戲，每個(gè)小游戲都必須在規(guī)定期限ti前完成(1≤ti≤n)。如果一個(gè)游戲沒(méi)能在規(guī)定期限前完成，則要從獎(jiǎng)勵(lì)費(fèi)m元中扣去一部分錢wi，wi為自然數(shù)，不同的游戲扣去的錢是不一樣的。當(dāng)然，每個(gè)游戲本身都很簡(jiǎn)單，保證每個(gè)參賽者都能在一個(gè)時(shí)段內(nèi)完成，而且都必須從整時(shí)段開(kāi)始。主持人只是想考考每個(gè)參賽者如何安排組織自己做游戲的順序。作為參賽者，小偉很想贏得冠軍，當(dāng)然更想贏取最多的錢！注意：比賽絕對(duì)不會(huì)讓參賽者賠錢!【輸入】輸入文件riddle.in，共4行。第1行為m，表示一開(kāi)始獎(jiǎng)勵(lì)給每位參賽者的錢；第2行為n，表示有n個(gè)小游戲；第3行有n個(gè)數(shù)，分別表示游戲1到n的規(guī)定完成期限；第4行有n個(gè)數(shù)，分別表示游戲1到n不能在規(guī)定期限前完成的扣款數(shù)?！据敵觥枯敵鑫募iddle.out，僅1行。表示小偉能贏取最多的錢?！緲永縭iddle.inriddle.out1000099507424314670605040302010【算法分析】因?yàn)椴煌男∮螒虿荒軠?zhǔn)時(shí)完成時(shí)具有不同的扣款權(quán)數(shù)，而且是最優(yōu)解問(wèn)題，所以本題很容易就想到了貪心法。貪心的主要思想是要讓扣款數(shù)值大的盡量準(zhǔn)時(shí)完成。這樣我們就先把這些任務(wù)按照扣款的數(shù)目進(jìn)行排序，把大的排在前面，先進(jìn)行放置。假如罰款最多的一個(gè)任務(wù)的完成期限是k，我們應(yīng)該把它安排在哪個(gè)時(shí)段完成呢?應(yīng)該放在第k個(gè)時(shí)段，因?yàn)榉旁?～k任意一個(gè)位置，效果都是一樣的。一旦出現(xiàn)一個(gè)不可能在規(guī)定時(shí)限前完成的任務(wù)，則把其扔到最大的一個(gè)空時(shí)間段，這樣必然是最優(yōu)的，因?yàn)椴荒芡瓿傻娜蝿?wù)，在任意一個(gè)時(shí)間段中罰款數(shù)目都是一樣的，具體實(shí)現(xiàn)請(qǐng)看下面的參考程序1。本題也可以有另外一種貪心算法，即先把所有的數(shù)據(jù)按照結(jié)束時(shí)間的先后排序，然后從前向后掃描。當(dāng)掃描到第n個(gè)時(shí)段，發(fā)現(xiàn)里面所分配的任務(wù)的結(jié)束時(shí)間等于n-1，那么就說(shuō)明在前面這些任務(wù)中必須舍棄一個(gè)，于是再掃描第1～n這n個(gè)時(shí)段，挑出一個(gè)最小的去掉并累加扣款值，然后再去調(diào)整排列順序，讓后面的元素填補(bǔ)前面的空缺，具體實(shí)現(xiàn)請(qǐng)看下面的參考程序2。17/17
3貪心法習(xí)題匯總3.3取火柴游戲源程序名match.???（pas,c,cpp）可執(zhí)行文件名match.exe輸入文件名match.in輸出文件名match.out【問(wèn)題描述】輸入k及k個(gè)整數(shù)n1，n2，…，nk，表示有k堆火柴棒，第i堆火柴棒的根數(shù)為ni；接著便是你和計(jì)算機(jī)取火柴棒的對(duì)弈游戲。取的規(guī)則如下：每次可以從一堆中取走若干根火柴，也可以一堆全部取走，但不允許跨堆取，也不允許不取。誰(shuí)取走最后一根火柴為勝利者。例如：k＝2，n1＝n2＝2，A代表你，P代表計(jì)算機(jī)，若決定A先?。篈：(2,2)→(1,2){從一堆中取一根}P：(1,2)→(1,1){從另一堆中取一根}A：(1,1)→(1,0)P：(1,0)→(0,0){P勝利}如果決定A后?。篜：(2,2)→(2,0)A：(2,0)→0,0){A勝利}又如k＝3，n1=1，n2＝2，n3＝3，A決定后取：P：(1,2,3)→(0,2,3)A：(0,2,3)→(0,2,2)A已將游戲歸結(jié)為(2,2)的情況，不管P如何取A都必勝。編一個(gè)程序，在給出初始狀態(tài)之后，判斷是先取必勝還是先取必?cái)?，如果是先取必勝，?qǐng)輸出第一次該如何取。如果是先取必?cái)?，則輸出“l(fā)ose”?！緲永?】match.inmatch.out343{表示第一次從第3堆取4個(gè)出來(lái)，必勝}369365{第一次取后的狀態(tài)}【樣例2】match.inmatch.out4lose{先取必?cái)15221910【算法分析】從問(wèn)題的描述分析，可以將問(wèn)題中的k堆火柴棒抽象為k個(gè)非負(fù)整數(shù)，而每取一次火柴棒可抽象為使其中的一個(gè)自然數(shù)變小，當(dāng)所有的數(shù)都變?yōu)?時(shí)，游戲結(jié)束，最后—次取火柴棒的人為勝方。當(dāng)k較小，且k堆火柴棒也都較小時(shí)，可使用遞推的方法來(lái)處理這個(gè)問(wèn)題，具體做法是從終了狀態(tài)(全零)反推出初始狀態(tài)的值是先取必勝還是先取必?cái)?，因?yàn)槟骋粻顟B(tài)的值可以從它的所有的取一次后的下一狀態(tài)得到，如果某狀態(tài)的所有的下一狀態(tài)都為先取必?cái)。瑒t這一狀態(tài)為先取必勝，否則為先取必?cái) ?7/17
4貪心法習(xí)題匯總但當(dāng)k和ni都很大時(shí)，上述方法很難行得通，為了解決這個(gè)問(wèn)題，首先引進(jìn)關(guān)于n個(gè)非負(fù)整數(shù)的奇偶狀態(tài)的定義：如果把n個(gè)非負(fù)整數(shù)都化成二進(jìn)制數(shù)，然后對(duì)n個(gè)二進(jìn)制數(shù)按位相加(不進(jìn)行進(jìn)位)，若每一位相加的結(jié)果都為偶數(shù)，則稱這n個(gè)非負(fù)整數(shù)的狀態(tài)為偶狀態(tài)，否則稱之為奇狀態(tài)?？梢宰C明：任何一個(gè)偶狀態(tài)在某一個(gè)數(shù)變小后一定成為奇狀態(tài)，而對(duì)任何一個(gè)奇狀態(tài)，必定可以通過(guò)將某一個(gè)數(shù)的值變小，使得改變后的狀態(tài)成為偶狀態(tài)。前一種情況是顯然的，因?yàn)橐粋€(gè)數(shù)變小以后其對(duì)應(yīng)的二進(jìn)制數(shù)至少有一位發(fā)生改變。這一位的改變就破壞了原來(lái)的偶狀態(tài)。后一種情況可以通過(guò)構(gòu)造的方法來(lái)證明，首先對(duì)任何一個(gè)奇狀態(tài)，從高位向低位尋找到第一位按位加之和為奇數(shù)的二進(jìn)制位，設(shè)這一位為第k位，則n個(gè)數(shù)的對(duì)應(yīng)的二進(jìn)制數(shù)中至少存在一個(gè)數(shù)，其第k位為1，將這個(gè)二進(jìn)制數(shù)的第k位變成0，則所有二進(jìn)制數(shù)的第k位上的數(shù)字之和就變成了偶數(shù)。然后再對(duì)這個(gè)數(shù)的比k位低的所有位作如下調(diào)整：如果所有二進(jìn)制數(shù)在該位按位加之和為偶數(shù)，則不改變?cè)撐坏闹担駝t改變?cè)摂?shù)在該位的值，若原來(lái)的值為0，則改為1，若原來(lái)的值為1，則改為0，這樣就構(gòu)造出了一個(gè)偶狀態(tài)，并且被改變的那個(gè)數(shù)一定變小了，因?yàn)檫@個(gè)數(shù)被改變的所有二進(jìn)制位中的最高位從1變成了0。如n＝3時(shí)，三堆火柴棒的數(shù)量分別為3，6，9，則3＝(0011)2，6＝(0110)2，9＝(1001)2，最高位之和為1，其中9對(duì)應(yīng)的二進(jìn)制數(shù)的最高位為1，將其變?yōu)?，次高位之和也是1，9對(duì)應(yīng)的二進(jìn)制數(shù)的次高位為0，根據(jù)證明過(guò)程將其變?yōu)?，最后二位數(shù)字之和均為偶數(shù)，無(wú)需作任何改變，這樣9＝(1001)2被變成了(0101)2=5，顯然，3=(0011)2，6=(0110)2，5=(0101)2是一個(gè)偶狀態(tài)。有了前面的分析，一種貪心算法就出來(lái)了。程序中用n個(gè)包含16個(gè)元素的數(shù)組（線性表）來(lái)存放對(duì)每個(gè)非負(fù)整數(shù)對(duì)應(yīng)的二進(jìn)制數(shù)，如b[i,0]存放第i個(gè)數(shù)的最低位，n個(gè)數(shù)的狀態(tài)取決于它們對(duì)應(yīng)的二進(jìn)制數(shù)的各位數(shù)字之和的奇偶性，而各位數(shù)字之和的奇偶性只需用0和1來(lái)表示，0表示偶，1表示奇。最后的狀態(tài)(全0)為偶狀態(tài)，所以開(kāi)始狀態(tài)為偶狀態(tài)時(shí)，先取必?cái)?，因?yàn)橄热『缶置孀兂闪似鏍顟B(tài)，后取方一定可將字取成偶狀態(tài)，直至取光為止。反之則先取必勝?！竞笥洝看蠹叶贾绹?guó)際象棋特級(jí)大師卡斯帕羅夫與IBM公司研制的“深藍(lán)”超級(jí)計(jì)算機(jī)進(jìn)行國(guó)際象棋人機(jī)大戰(zhàn)的事吧!有了以上算法后，我們也可以編寫出這樣一個(gè)游戲程序。讓程序代表計(jì)算機(jī)與人做取火柴棒游戲，由人或計(jì)算機(jī)先取，要求你編的程序能夠盡可能使計(jì)算機(jī)獲勝。17/17
5貪心法習(xí)題匯總3.4加工生產(chǎn)調(diào)度源程序名prod.???（pas,c,cpp）可執(zhí)行文件名prod.exe輸入文件名prod.in輸出文件名prod.out【問(wèn)題描述】某工廠收到了n個(gè)產(chǎn)品的訂單，這n個(gè)產(chǎn)品分別在A、B兩個(gè)車間加工，并且必須先在A車間加工后才可以到B車間加工。某個(gè)產(chǎn)品i在A、B兩車間加工的時(shí)間分別為Ai、Bi。怎樣安排這n個(gè)產(chǎn)品的加工順序，才能使總的加工時(shí)間最短。這里所說(shuō)的加工時(shí)間是指：從開(kāi)始加工第一個(gè)產(chǎn)品到最后所有的產(chǎn)品都已在A、B兩車間加工完畢的時(shí)間?！据斎搿康谝恍袃H—個(gè)數(shù)據(jù)n(06貪心法習(xí)題匯總設(shè)S＝7貪心法習(xí)題匯總其中，按照上面的假設(shè)，有T<=T’，所以有：從而有：即：這說(shuō)是所謂的Johnson公式，也就是說(shuō)在此公式成立的條件下，優(yōu)先安排任務(wù)Ji在Jj之前可以得到最優(yōu)解。也就是在A車間加工時(shí)間短的安排在前面，在B車間加工時(shí)間短的任務(wù)安排在后面。以樣例數(shù)據(jù)為例：（A1,A2,A3,A4,A5）=（3,5,8,7,10）（B1,B2,B3,B4,B5）=（6,2,1,4,9）則（m1,m2,m3,m4,m5）=（3,2,1,4,9）排序之后為：（m3,m2,m1,m4,m5）處理m3，因?yàn)閙3=B3，所以m3安排在后面（，，，，3）；處理m2，因?yàn)閙2=B2，所以m2安排在后面（，，，2，3）；處理m1，因?yàn)閙1=A1，所以m1安排在前面（1，，，2，3）；處理m4，因?yàn)閙4=B4，所以m4安排在后面（1，，4，2，3）；處理m5，因?yàn)閙5=B5，所以m5安排在后面（1，5，4，2，3）。從而得到加工的順序1，5，4，2，3。計(jì)算出最短的加工時(shí)間34?！狙a(bǔ)充說(shuō)明】由于本題的原始數(shù)據(jù)并沒(méi)有保證數(shù)據(jù)間沒(méi)有重復(fù)，所以在數(shù)據(jù)有重復(fù)的情況下生產(chǎn)調(diào)度安排并不是惟一的。但是最少的加工時(shí)間是惟一的。17/17
8貪心法習(xí)題匯總3.5最大乘積源程序名maxmul.???（pas,c,cpp）可執(zhí)行文件名maxmul.exe輸入文件名maxmul.in輸出文件名maxmul.out【問(wèn)題描述】一個(gè)正整數(shù)一般可以分為幾個(gè)互不相同的自然數(shù)的和，如3=1+2，4=1+3，5＝1+4=2+3，6=1+5＝2+4，…。現(xiàn)在你的任務(wù)是將指定的正整數(shù)n分解成若干個(gè)互不相同的自然數(shù)的和，且使這些自然數(shù)的乘積最大?！据斎搿恐灰粋€(gè)正整數(shù)n，(3≤n≤10000)?！据敵觥康谝恍惺欠纸夥桨?，相鄰的數(shù)之間用一個(gè)空格分開(kāi)，并且按由小到大的順序。第二行是最大的乘積。【樣例】maxmul.inmaxmul.out1023530【算法分析】初看此題，很容易想到用回溯法進(jìn)行搜索，但是這里的n范圍比較大，最多到10000，如果盲目搜索，運(yùn)行時(shí)間比較長(zhǎng)，效率很低，對(duì)于部分?jǐn)?shù)據(jù)可能得到結(jié)果，對(duì)于大部分?jǐn)?shù)據(jù)會(huì)超時(shí)或棧溢出。先來(lái)看看幾個(gè)n比較小的例子，看能否從中找出規(guī)律：n分解方案最大的乘積5236624873412835159234241023530可以發(fā)現(xiàn)，將n分解成a1,a2,a3,a4,…,am這m個(gè)自然數(shù)，該序列為從2開(kāi)始的一串由小到大的自然數(shù)，如果a1為1，則對(duì)乘積沒(méi)有影響，而且使n減少，沒(méi)有實(shí)際意義，只有特殊情況如n為3、4時(shí)才可能用上。設(shè)h>＝5，可以證明當(dāng)將h拆分為兩個(gè)不相同的部分并且兩部分都大于1時(shí)兩部分的乘積大于h。證明如下：將h分為兩部分：a，h-a其中2<＝a2*a，所以a*(h-a)-h>2*a*(a-1)-a*a=a*a-2*a=a*(a-2)又因?yàn)閍>＝2，所以a*(a-2)>=0，所以a*(h-a)-h>O即a*(h-a)>h。從上面的證明可以看出，對(duì)于指定的正整數(shù)，如果其大于等于5，將它拆分為不同的部分后乘積變大，對(duì)于中間結(jié)果也是如此。因此可以將指定的n，依次拆成a1+a2+a3+a4+…17/17
9貪心法習(xí)題匯總+am，乘積最大?，F(xiàn)在的問(wèn)題是如何拆分才能保證n＝a1+a2+a3+a4+…+am呢?可以先這樣取：當(dāng)和不足n時(shí)，a1取2，a2取3，…，am-1取m，即從2開(kāi)始按照自然數(shù)的順序取數(shù)，最后剩余的數(shù)給am，如果am<=am-1，此時(shí)am跟前面的數(shù)字出現(xiàn)了重復(fù)，則把a(bǔ)m從后面開(kāi)始平均分布給前面的m-1個(gè)數(shù)。為什么要從后面開(kāi)始往前呢?同樣是考慮數(shù)據(jù)不出現(xiàn)重復(fù)的問(wèn)題，如果是從前面往后面來(lái)平均分配，如2加上1以后變成3，就跟后面的已有的3出現(xiàn)了重復(fù)。這樣操作到底是否正確、是否能保證乘積最大呢?還要加以證明。證明過(guò)程如下：設(shè)兩個(gè)整數(shù)a，b的和為2s，且a<>b，設(shè)a＝s-1，則b＝s+1，a*b=(s-1)*(s+1)=s2-1，如果a=s-2，則b＝s+2，a*b＝(s-2)*(s+2)＝s2-4。a-b的絕對(duì)值越小，乘積的常數(shù)項(xiàng)越大，即乘積越大，上面的序列a1,a2,a3,a4,…,am正好滿足了a-b的絕對(duì)值最小。但是還要注意兩個(gè)特例就是n=3和n=4的情況，它們的分解方案分別為1，2和1，3，乘積分別為2和3。以n=10為例，先拆分為：10=2+3+4+1，最后一項(xiàng)為1，比4小，將其分配給前面的一項(xiàng)，得到10=2+3+5，所以最大的乘積為2*3*5＝30。以n=20為例，拆分為：20=2+3+4+5+6，正好是連續(xù)自然數(shù)的和，所以最大乘積為2*3*4*5*6=720。再以n=26為例，先拆分為：26=2+3+4+5+6+6，因?yàn)樽詈笠豁?xiàng)為6，不比最后第二項(xiàng)大，所以將其平均分給前面的項(xiàng)，優(yōu)先考慮后面的項(xiàng)，即前面的4項(xiàng)各分到1，笫5項(xiàng)6分到2，最后是26＝3+4+5+6+8，所以最大的乘積為3*4*5*6*8＝2880。由于n可能大到10000，分解之后的各項(xiàng)乘積位數(shù)比較多，超過(guò)普通的數(shù)據(jù)類型的位數(shù)，所以要用到高精度運(yùn)算來(lái)進(jìn)行整數(shù)的乘法運(yùn)算，將結(jié)果保存在數(shù)組里。本題的貪心策略就是：要使乘積最大，盡可能地將指定的n(n>4)拆分成從2開(kāi)始的連續(xù)的自然數(shù)的和，如果最后有剩余的數(shù)，將這個(gè)剩余的數(shù)在優(yōu)先考慮后面項(xiàng)的情況下平均分給前面的各項(xiàng)?；舅惴枋鋈缦拢海?）拆分過(guò)程拆分的數(shù)a先取2；當(dāng)n>a時(shí)做Begin選擇a作為一項(xiàng)；a增加1；n減少a；End；如果n>0，那么將n從最后一項(xiàng)開(kāi)始平均分給各項(xiàng)；如果n還大于0，再?gòu)淖詈笠豁?xiàng)開(kāi)始分一次；（2）求乘積設(shè)置一個(gè)數(shù)組來(lái)存放乘積，初始狀態(tài)位數(shù)為1，結(jié)果為1；將上面拆分的各項(xiàng)依次跟數(shù)組各項(xiàng)相乘并考慮進(jìn)位；17/17
10貪心法習(xí)題匯總3.6種樹(shù)源程序名trees.???（pas,c,cpp）可執(zhí)行文件名trees.exe輸入文件名trees.in輸出文件名trees.out【問(wèn)題描述】一條街的一邊有幾座房子。因?yàn)榄h(huán)保原因居民想要在路邊種些樹(shù)。路邊的地區(qū)被分割成塊，并被編號(hào)成1..N。每個(gè)部分為一個(gè)單位尺寸大小并最多可種一棵樹(shù)。每個(gè)居民想在門前種些樹(shù)并指定了三個(gè)號(hào)碼B，E，T。這三個(gè)數(shù)表示該居民想在B和E之間最少種T棵樹(shù)。當(dāng)然，B≤E，居民必須記住在指定區(qū)不能種多于區(qū)域地塊數(shù)的樹(shù)，所以T≤E-B+l。居民們想種樹(shù)的各自區(qū)域可以交叉。你的任務(wù)是求出能滿足所有要求的最少的樹(shù)的數(shù)量。寫一個(gè)程序完成以下工作：*從trees.in讀入數(shù)據(jù)*計(jì)算最少要種樹(shù)的數(shù)量和位置*把結(jié)果寫到trees.out【輸入】第一行包含數(shù)據(jù)N，區(qū)域的個(gè)數(shù)(011貪心法習(xí)題匯總3.7餐巾源程序名napkin.???（pas,c,cpp）可執(zhí)行文件名napkin.exe輸入文件名napkin.in輸出文件名napkin.out【問(wèn)題描述】一個(gè)餐廳在相繼的N天里，第i天需要Ri塊餐巾(i=l，2，…，N)。餐廳可以從三種途徑獲得餐巾。(1)購(gòu)買新的餐巾，每塊需p分；(2)把用過(guò)的餐巾送到快洗部，洗一塊需m天，費(fèi)用需f分(fm)，費(fèi)用需s分(s12貪心法習(xí)題匯總中數(shù)組need存放每天需用的餐巾數(shù)，數(shù)組fromslow記錄每天來(lái)自慢洗的餐巾數(shù)。數(shù)組fromfast記錄每天來(lái)自快洗的餐巾數(shù)，數(shù)組buy記錄每天購(gòu)買的餐巾數(shù)。變量restslow存儲(chǔ)當(dāng)天可供選用的已經(jīng)慢洗好的餐巾數(shù)。這個(gè)算法的數(shù)量級(jí)為O(n)，其中n為所有天中需用的餐巾數(shù)之總和。17/17
13貪心法習(xí)題匯總3.8馬拉松接力賽源程序名marathon.???（pas,c,cpp）可執(zhí)行文件名marathon.exe輸入文件名marath.in輸出文件名marath.out【問(wèn)題描述】某城市冬季舉辦環(huán)城25km馬拉松接力賽，每個(gè)代表隊(duì)有5人參加比賽，比賽要求每個(gè)的每名參賽選手只能跑一次，一次至少跑1km、最多只能跑10km，而且每個(gè)選手所跑的公里數(shù)必須為整數(shù)，即接力的地方在整公里處。劉老師作為學(xué)校代表隊(duì)的教練，精心選擇了5名長(zhǎng)跑能手，進(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速度快……也就是說(shuō)連續(xù)跑的路程越長(zhǎng)，速度越慢，當(dāng)然也有特殊的，就是速度不會(huì)變慢，但是絕不可能變快?！据斎搿?行數(shù)據(jù)，分別是1到5號(hào)隊(duì)員的測(cè)試數(shù)據(jù)，每行的10個(gè)整數(shù)，表示某一個(gè)運(yùn)動(dòng)員盡力連續(xù)跑1km、2km、…、10km所用的時(shí)間?！据敵觥?jī)尚?，第一行是最短的時(shí)間，第二行是五個(gè)數(shù)據(jù)，分別是1到5號(hào)隊(duì)員各自連續(xù)跑的公里數(shù)。【樣例】marath.inmarath.out333700120017102240261332453956477858999748300610960137018002712383448345998768265545298612990156021092896379047475996765428957789013811976273438765678689098763126339951467184526343636481259998123【算法分析】初看此題，好象是一個(gè)排列問(wèn)題，選取5個(gè)10之間的數(shù)，共有10*10*10*10*10＝100000種情況，對(duì)每一種情況，再看其和是否為25，在和為25的情況下再計(jì)算所用的總時(shí)間，找出其中最少的。這種枚舉的方法，肯定能找到最優(yōu)解，但是這樣做的效率不高，執(zhí)行時(shí)間長(zhǎng)，這里是5個(gè)選手還行，如果更多，如15個(gè)選手，就要對(duì)l015種可能情況進(jìn)行判定，再快的計(jì)算機(jī)也要較長(zhǎng)的時(shí)間來(lái)執(zhí)行。因?yàn)檫\(yùn)動(dòng)員連續(xù)跑一公里要比連續(xù)跑兩公里速度快、連續(xù)跑兩公里又要比連續(xù)跑三公里速度快……也就是說(shuō)連續(xù)跑的路程越長(zhǎng)，速度越慢，所以我們可以將每個(gè)選手的所跑時(shí)間進(jìn)行分段處理，計(jì)算出各自所跑每一公里所用的時(shí)間。又因?yàn)橐竺總€(gè)選手至少跑一公里，先給每一個(gè)人分配一公里。剩下的里程由哪個(gè)選手來(lái)跑呢?這時(shí)檢查各自所跑第二公里所用的時(shí)間，哪個(gè)用的時(shí)間最短就選這個(gè)選手繼續(xù)跑一公里，因?yàn)檫@樣做可以保證當(dāng)前所用的時(shí)間最少，這個(gè)所手所跑的公里數(shù)增加1。下一公里繼續(xù)用這種方法選，看當(dāng)前要跑一公里哪個(gè)用的時(shí)間最短就選誰(shuí)，選了誰(shuí)，誰(shuí)所跑的公里數(shù)增加l，下面要檢查的時(shí)間段就是他的下一段……如此反復(fù)直到25公里分配完為止。17/17
14貪心法習(xí)題匯總對(duì)于每個(gè)運(yùn)動(dòng)員跑各公里所用的時(shí)間不一定要單獨(dú)計(jì)算出來(lái)，如它跑第5公里所用的時(shí)間等于他連續(xù)跑完5公里所用的時(shí)間減去他連續(xù)跑4公里所用的時(shí)間。本題所用的貪心策略就是：先分配每個(gè)運(yùn)動(dòng)員跑一公里；剩下的20公里始終選擇所有運(yùn)動(dòng)員當(dāng)中下一公里跑的時(shí)間最短的，直到分配完。這樣局部的最優(yōu)保證整體的最優(yōu)。17/17
15貪心法習(xí)題匯總3.9線性存儲(chǔ)問(wèn)題源程序名storage.???（pas,c,cpp）可執(zhí)行文件名storage.exe輸入文件名storage.in輸出文件名storage.out【問(wèn)題描述】磁帶等存儲(chǔ)介質(zhì)存儲(chǔ)信息時(shí)基本上都是一種線性存儲(chǔ)的方式，線性存儲(chǔ)方式雖然簡(jiǎn)單，但查詢檢索時(shí)往往要經(jīng)過(guò)一些其它信息，不象磁盤等存儲(chǔ)介質(zhì)在目錄區(qū)找到后可直接定位到某一區(qū)城，因此線性存儲(chǔ)總有它的局限性。但是由于磁帶等線性存儲(chǔ)有簡(jiǎn)單、保存時(shí)間相對(duì)較長(zhǎng)等優(yōu)點(diǎn)，現(xiàn)在仍然在使用。如果有n段信息資料要線性存儲(chǔ)在某種存儲(chǔ)介質(zhì)上，它們的長(zhǎng)度分別是L1，L2，…，Ln，存儲(chǔ)介質(zhì)能夠保存下所有這些信息，假設(shè)它們的使用(查詢檢索)的頻率分別是F1，F(xiàn)2，…，F(xiàn)n，要如何存儲(chǔ)這些信息資料才能使平均檢索時(shí)間最短。你的任務(wù)就是編程安排一種平均檢索時(shí)間最短的方案。【輸入】第一行是一個(gè)正整數(shù)n(n<10000)，接下來(lái)是n行數(shù)據(jù)，每行兩個(gè)整數(shù)分別是第1段信息的長(zhǎng)度(1到10000之間)和使用的頻率(萬(wàn)分比，在0到9000之間)，總的頻率之和為10000。所輸入數(shù)據(jù)均不要判錯(cuò)?！据敵觥恳来未鎯?chǔ)信息段的編號(hào)。每個(gè)數(shù)據(jù)之間用一個(gè)空格隔開(kāi)?！緲永縮torage.instorage.out541352104000201000301000351500122500【算法分析】根據(jù)統(tǒng)計(jì)的基本原理，n段信息資料的使用（查詢檢索）的頻率之和應(yīng)為1，即F1+F2+…+Fn=1，如果總的檢索次數(shù)為m，第I段信息資料使用的次數(shù)為m*Fi，設(shè)平均檢索速度為v單位長(zhǎng)度/單位時(shí)間，而它的長(zhǎng)度為L(zhǎng)i，每次所用的時(shí)間為Ti-1+Li/V，其中Ti-1為通過(guò)安排在第I個(gè)信息段前面的所有信息所要的時(shí)間，訪問(wèn)信息段I所有次數(shù)總的時(shí)間時(shí)：m*Fi*(Ti-1+Li/v)。因?yàn)樯媳磉_(dá)式中m、v可看作是常數(shù)，所以單一訪問(wèn)時(shí)間Fi與Li及前面的安排有關(guān)，每段信息均是這樣，由此我們可采用如下的貪心方法：根據(jù)(頻率*長(zhǎng)度)進(jìn)行由大到小的排序，然后根據(jù)這個(gè)排序安排某一信息段在相應(yīng)位置，從而得到的總的檢索時(shí)間最短，也就是平均檢索時(shí)間最短。17/17
16貪心法習(xí)題匯總3.10扇區(qū)填數(shù)源程序名fan.???（pas,c,cpp）可執(zhí)行文件名fan.exe輸入文件名fan.in輸出文件名fan.out【問(wèn)題描述】有一個(gè)圓，當(dāng)輸入一個(gè)整數(shù)n(1≤n≤6)后，它被分成n個(gè)扇區(qū)，請(qǐng)你為每一扇區(qū)選擇一個(gè)自然數(shù)(大于0的整數(shù))。向各個(gè)扇區(qū)放入數(shù)之后，你可以從單個(gè)扇區(qū)中選出—個(gè)數(shù)，也可以從相鄰的兩個(gè)或多個(gè)扇區(qū)中各選一個(gè)數(shù)，相加后形成一個(gè)新的數(shù)，請(qǐng)使用這些整數(shù)形成一個(gè)連續(xù)的整數(shù)序列，：1，2，3，…，i，你的任務(wù)是使i盡可能地大?！据斎搿恐灰粋€(gè)整數(shù)n(1<＝n<＝6)?！据敵觥康谝恍惺亲畲蟮膇，接下來(lái)的幾行是所有能達(dá)到最大i的填法。由于圓里不分順序，所以同一種填法可以有多種輸出。為了減少這種情況，這里規(guī)定從1，開(kāi)始輸出(因?yàn)檫B續(xù)數(shù)里要有1，所以所填的數(shù)中肯定有1)。【樣例】fan.infan.out111【算法分析】假設(shè)圓已經(jīng)被分成了n個(gè)扇區(qū)，并且已經(jīng)在這n個(gè)扇區(qū)中填好了數(shù)字，先來(lái)看看填好數(shù)字后最多有多少種選擇連續(xù)的數(shù)字并求和的方法，以N＝4為例：?jiǎn)为?dú)選一個(gè)，有n種即1、2、3、4；選擇相鄰兩個(gè)也有n種即12、23、34、41選擇相鄰三個(gè)也有n種即123、234、341、412；選擇相鄰四個(gè)只有一種即1234?？偣灿衝*(n-1)+1種，當(dāng)n=4時(shí)有13種。如果每一種選擇所求的和都不同，那么能夠構(gòu)成的最多有n*(n-1)+1個(gè)不同的數(shù)。我們當(dāng)然希望能夠達(dá)到的最大的連續(xù)數(shù)就是從1到n*(n-1)+1了，如N=4時(shí)就是1到13。現(xiàn)在的問(wèn)題是如何保證這n*(n-1)+1個(gè)數(shù)就是從1到n*(n-1)+1。在填數(shù)時(shí)首先填1，接下來(lái)的n-1個(gè)數(shù)都保證不同且最小為2，再看其他的取相鄰的多個(gè)數(shù)的情況了。在n<＝6的情況下都能滿足這個(gè)要求，對(duì)于n>6時(shí)就不一定了。從這種最優(yōu)策略出發(fā)，再結(jié)合回溯法找出所有可能的情況。17/17
