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