貪心法習(xí)題匯總

1、精選優(yōu)質(zhì)文檔-傾情為你奉上貪心法習(xí)題匯總排隊接水源程序名 .?（, , ）可執(zhí)行文件名 輸入文件名 輸出文件名 【問題描述】 有個人在一個水龍頭前排隊接水，假如每個人接水的時間為，請編程找出這個人排隊的一種順序，使得個人的平均等待時間最小。【輸入】 輸入文件共兩行，第一行為；第二行分別表示第個人到第個人每人的接水時間，每個數(shù)據(jù)之間有個空格?！据敵觥?輸出文件有兩行，第一行為一種排隊順序，即到的一種排列；第二行為這種排列方案下的平均等待時間(輸出結(jié)果精確到小數(shù)點后兩位)?！緲永俊舅惴ǚ治觥科骄却龝r間是每個人的等待時間之和再除以，因為是一個常數(shù)，所以等待時間之和最小，也就是平均等待時間最小。假

2、設(shè)是按照的自然順序排列的，則這個問題就是求以下公式的最小值：如果用窮舉的方法求解，就需要我們產(chǎn)生個人的所有不同排列，然后計算每種排列所需要等待的時間之和，再“打擂臺”得到最小值，但這種方法需要進行!次求和以及判斷，時間復(fù)雜度很差！其實，我們仔細研究一下上面的公式，發(fā)現(xiàn)可以改寫成如下形式：這個公式何時取最小值呢？對于任意一種排列, , , , ，當時，取到最小值。如何證明呢？方法如下：因為假設(shè)<，而<，這是的和為，而把和互換位置，設(shè)新的和為，則：我們發(fā)現(xiàn)上述恒大于，所以也說明了任何次序的改變，都會導(dǎo)致等待時間的增加。從而證明了我們的設(shè)想。既然如此，我們就得到了一種最有貪心策略：把接水

3、時間少的人盡可能排在前面。這樣一樣，問題的本質(zhì)就變成：把個等待時間按非遞減順序排列，輸出這種排列，并求出這種排列下的平均等待時間。智力大沖浪源程序名 .?（, , ）可執(zhí)行文件名 輸入文件名 輸出文件名 【問題描述】 小偉報名參加中央電視臺的智力大沖浪節(jié)目。本次挑戰(zhàn)賽吸引了眾多參賽者，主持人為了表彰大家的勇氣，先獎勵每個參賽者元。先不要太高興！因為這些錢還不一定都是你的？！接下來主持人宣布了比賽規(guī)則： 首先，比賽時間分為個時段()，它又給出了很多小游戲，每個小游戲都必須在規(guī)定期限前完成()。如果一個游戲沒能在規(guī)定期限前完成，則要從獎勵費元中扣去一部分錢，為自然數(shù)，不同的游戲扣去的錢是不一樣的。

4、當然，每個游戲本身都很簡單，保證每個參賽者都能在一個時段內(nèi)完成，而且都必須從整時段開始。主持人只是想考考每個參賽者如何安排組織自己做游戲的順序。作為參賽者，小偉很想贏得冠軍，當然更想贏取最多的錢！注意：比賽絕對不會讓參賽者賠錢!【輸入】輸入文件，共行。第行為，表示一開始獎勵給每位參賽者的錢；第行為，表示有個小游戲；第行有個數(shù)，分別表示游戲到的規(guī)定完成期限；第行有個數(shù)，分別表示游戲到不能在規(guī)定期限前完成的扣款數(shù)?！据敵觥枯敵鑫募?，僅行。表示小偉能贏取最多的錢。【樣例】【算法分析】 因為不同的小游戲不能準時完成時具有不同的扣款權(quán)數(shù)，而且是最優(yōu)解問題，所以本題很容易就想到了貪心法。貪心的主要思想是要

5、讓扣款數(shù)值大的盡量準時完成。這樣我們就先把這些任務(wù)按照扣款的數(shù)目進行排序，把大的排在前面，先進行放置。假如罰款最多的一個任務(wù)的完成期限是，我們應(yīng)該把它安排在哪個時段完成呢?應(yīng)該放在第個時段，因為放在任意一個位置，效果都是一樣的。一旦出現(xiàn)一個不可能在規(guī)定時限前完成的任務(wù)，則把其扔到最大的一個空時間段，這樣必然是最優(yōu)的，因為不能完成的任務(wù)，在任意一個時間段中罰款數(shù)目都是一樣的，具體實現(xiàn)請看下面的參考程序。 本題也可以有另外一種貪心算法，即先把所有的數(shù)據(jù)按照結(jié)束時間的先后排序，然后從前向后掃描。 當掃描到第個時段，發(fā)現(xiàn)里面所分配的任務(wù)的結(jié)束時間等于，那么就說明在前面這些任務(wù)中必須舍棄一個，于是再掃描

6、第這個時段，挑出一個最小的去掉并累加扣款值，然后再去調(diào)整排列順序，讓后面的元素填補前面的空缺，具體實現(xiàn)請看下面的參考程序。取火柴游戲源程序名 .?（, , ）可執(zhí)行文件名 輸入文件名 輸出文件名 【問題描述】 輸入及個整數(shù)，表示有堆火柴棒，第堆火柴棒的根數(shù)為；接著便是你和計算機取火柴棒的對弈游戲。取的規(guī)則如下：每次可以從一堆中取走若干根火柴，也可以一堆全部取走，但不允許跨堆取，也不允許不取。 誰取走最后一根火柴為勝利者。 例如：，代表你，代表計算機，若決定先?。?：()() 從一堆中取一根 ：()() 從另一堆中取一根 ：()() ：() () 勝利 如果決定后?。?：()() ：() ) 勝

7、利 又如，決定后取： ：()() ：()() 已將游戲歸結(jié)為()的情況，不管如何取都必勝。 編一個程序，在給出初始狀態(tài)之后，判斷是先取必勝還是先取必敗，如果是先取必勝，請輸出第一次該如何取。如果是先取必敗，則輸出“”。【樣例】 表示第一次從第堆取個出來，必勝 第一次取后的狀態(tài)【樣例】先取必敗【算法分析】 從問題的描述分析，可以將問題中的堆火柴棒抽象為個非負整數(shù)，而每取一次火柴棒可抽象為使其中的一個自然數(shù)變小，當所有的數(shù)都變?yōu)闀r，游戲結(jié)束，最后次取火柴棒的人為勝方。 當較小，且堆火柴棒也都較小時，可使用遞推的方法來處理這個問題，具體做法是從終了狀態(tài)(全零)反推出初始狀態(tài)的值是先取必勝還是先取必敗

8、，因為某一狀態(tài)的值可以從它的所有的取一次后的下一狀態(tài)得到，如果某狀態(tài)的所有的下一狀態(tài)都為先取必敗，則這一狀態(tài)為先取必勝，否則為先取必敗。 但當和都很大時，上述方法很難行得通，為了解決這個問題，首先引進關(guān)于個非負整數(shù)的奇偶狀態(tài)的定義：如果把個非負整數(shù)都化成二進制數(shù)，然后對個二進制數(shù)按位相加(不進行進位)，若每一位相加的結(jié)果都為偶數(shù)，則稱這個非負整數(shù)的狀態(tài)為偶狀態(tài)，否則稱之為奇狀態(tài)?？梢宰C明：任何一個偶狀態(tài)在某一個數(shù)變小后一定成為奇狀態(tài)，而對任何一個奇狀態(tài)，必定可以通過將某一個數(shù)的值變小，使得改變后的狀態(tài)成為偶狀態(tài)。前一種情況是顯然的，因為一個數(shù)變小以后其對應(yīng)的二進制數(shù)至少有一位發(fā)生改變。這一位的

9、改變就破壞了原來的偶狀態(tài)。后一種情況可以通過構(gòu)造的方法來證明，首先對任何一個奇狀態(tài)，從高位向低位尋找到第一位按位加之和為奇數(shù)的二進制位，設(shè)這一位為第位，則個數(shù)的對應(yīng)的二進制數(shù)中至少存在一個數(shù)，其第位為，將這個二進制數(shù)的第位變成，則所有二進制數(shù)的第位上的數(shù)字之和就變成了偶數(shù)。然后再對這個數(shù)的比位低的所有位作如下調(diào)整：如果所有二進制數(shù)在該位按位加之和為偶數(shù)，則不改變該位的值，否則改變該數(shù)在該位的值，若原來的值為，則改為，若原來的值為，則改為，這樣就構(gòu)造出了一個偶狀態(tài)，并且被改變的那個數(shù)一定變小了，因為這個數(shù)被改變的所有二進制位中的最高位從變成了。 如時，三堆火柴棒的數(shù)量分別為，則()，()，()，

10、最高位之和為，其中對應(yīng)的二進制數(shù)的最高位為，將其變?yōu)?，次高位之和也是，對?yīng)的二進制數(shù)的次高位為，根據(jù)證明過程將其變?yōu)椋詈蠖粩?shù)字之和均為偶數(shù)，無需作任何改變，這樣()被變成了()，顯然，()，()，()是一個偶狀態(tài)。 有了前面的分析，一種貪心算法就出來了。程序中用個包含個元素的數(shù)組（線性表）來存放對每個非負整數(shù)對應(yīng)的二進制數(shù)，如, 存放第個數(shù)的最低位，個數(shù)的狀態(tài)取決于它們對應(yīng)的二進制數(shù)的各位數(shù)字之和的奇偶性，而各位數(shù)字之和的奇偶性只需用和來表示，表示偶，表示奇。最后的狀態(tài)(全)為偶狀態(tài)，所以開始狀態(tài)為偶狀態(tài)時，先取必敗，因為先取后局面變成了奇狀態(tài)，后取方一定可將字取成偶狀態(tài)，直至取光為止。反

11、之則先取必勝。【后記】大家都知道國際象棋特級大師卡斯帕羅夫與公司研制的“深藍”超級計算機進行國際象棋人機大戰(zhàn)的事吧! 有了以上算法后，我們也可以編寫出這樣一個游戲程序。讓程序代表計算機與人做取火柴棒游戲，由人或計算機先取，要求你編的程序能夠盡可能使計算機獲勝。加工生產(chǎn)調(diào)度源程序名 .?（, , ）可執(zhí)行文件名 輸入文件名 輸出文件名 【問題描述】 某工廠收到了個產(chǎn)品的訂單，這個產(chǎn)品分別在、兩個車間加工，并且必須先在車間加工后才可以到車間加工。 某個產(chǎn)品在、兩車間加工的時間分別為、。怎樣安排這個產(chǎn)品的加工順序，才能使總的加工時間最短。這里所說的加工時間是指：從開始加工第一個產(chǎn)品到最后所有的產(chǎn)品都

12、已在、兩車間加工完畢的時間?！据斎搿康谝恍袃H個數(shù)據(jù)(<<)，表示產(chǎn)品的數(shù)量。接下來個數(shù)據(jù)是表示這個產(chǎn)品在車間加工各自所要的時間(都是整數(shù))。最后的個數(shù)據(jù)是表示這個產(chǎn)品在車間加工各自所要的時間(都是整數(shù))?！据敵觥?第一行一個數(shù)據(jù)，表示最少的加工時間； 第二行是一種最小加工時間的加工順序?！緲永俊舅惴ǚ治觥?本題是要求一個加工順序使得總的加工時間最少，而要使加工時間最少，就是讓各車間的空閑時間最少。一旦車間開始加工，便會不停地進行加工(我們不要去管車間是否能夠一直生產(chǎn)，因為他們有三班，可以時間不停地運轉(zhuǎn))。關(guān)鍵是車間在生產(chǎn)的過程中，有可能要等待車間的初加工產(chǎn)品。很顯然所安排的第一個

13、產(chǎn)品在車間加工時，車間是要等待的，最后一個產(chǎn)品在車間加工時，車間已經(jīng)完成了任務(wù)。 要使總的空閑時間最少，就要把在車間加工時間最短的部件優(yōu)先加工，這樣使得車間能以最快的速度開始加工；把放在車間加工時間最短的產(chǎn)品放在最后加工，這樣使得最后車間的空閑時間最少。 設(shè)計出這樣的貪心法： 設(shè)， 將按照由小到大的順序排序，然后從第一個開始處理，如果，則將它安排在從頭開始的已經(jīng)安排的生產(chǎn)順序后面，如果，則將它安排在從尾開始的已安排的生產(chǎn)順序前面。 這種安排是否是最少的加工時間，還要通過數(shù)學(xué)證明。證明如下： 設(shè)<，)，是等待加工的作業(yè)序列，如果車間開始加工中的產(chǎn)品時，車間還在加工其他產(chǎn)品，時刻后車間就可利

14、用車間加工過的產(chǎn)品。在這樣的條件下，加工中任務(wù)所要的最短時間(, )(，, )，其中，。圖是加工作業(yè)時車間等待車間的情況：圖 等的情況圖是加工作業(yè)時車間等待車間的情形：圖 等的情況假設(shè)最佳的方案中，先加工作業(yè)，然后再加工作業(yè)，則有：如果，則如果，則如果，則如果將作業(yè)和作業(yè)的加工順序調(diào)整，則有：其中，按照上面的假設(shè)，有<，所以有：從而有：即：這說是所謂的公式，也就是說在此公式成立的條件下，優(yōu)先安排任務(wù)在之前可以得到最優(yōu)解。也就是在車間加工時間短的安排在前面，在車間加工時間短的任務(wù)安排在后面。以樣例數(shù)據(jù)為例：（, , , , ）（, , , , ）（, , , , ）（, , , , ）則（

15、, , , , ）（, , , , ）排序之后為：（, , , , ）處理，因為，所以安排在后面（，）；處理，因為，所以安排在后面（，）；處理，因為，所以安排在前面（，）；處理，因為，所以安排在后面（，）；處理，因為，所以安排在后面（，）。從而得到加工的順序，。計算出最短的加工時間?！狙a充說明】由于本題的原始數(shù)據(jù)并沒有保證數(shù)據(jù)間沒有重復(fù)，所以在數(shù)據(jù)有重復(fù)的情況下生產(chǎn)調(diào)度安排并不是惟一的。但是最少的加工時間是惟一的。最大乘積源程序名 .?（, , ）可執(zhí)行文件名 輸入文件名 輸出文件名 【問題描述】 一個正整數(shù)一般可以分為幾個互不相同的自然數(shù)的和，如，。 現(xiàn)在你的任務(wù)是將指定的正整數(shù)分解成若干個

16、互不相同的自然數(shù)的和，且使這些自然數(shù)的乘積最大?！据斎搿恐灰粋€正整數(shù)，()?！据敵觥康谝恍惺欠纸夥桨福噜彽臄?shù)之間用一個空格分開，并且按由小到大的順序。第二行是最大的乘積?！緲永俊舅惴ǚ治觥?初看此題，很容易想到用回溯法進行搜索，但是這里的范圍比較大，最多到，如果盲目搜索，運行時間比較長，效率很低，對于部分數(shù)據(jù)可能得到結(jié)果，對于大部分數(shù)據(jù)會超時或棧溢出。先來看看幾個比較小的例子，看能否從中找出規(guī)律：分解方案最大的乘積 可以發(fā)現(xiàn)，將分解成, , , , 這個自然數(shù)，該序列為從開始的一串由小到大的自然數(shù)，如果為，則對乘積沒有影響，而且使減少，沒有實際意義，只有特殊情況如為、時才可能用上。 設(shè)&g

17、t;，可以證明當將拆分為兩個不相同的部分并且兩部分都大于時兩部分的乘積大于。證明如下： 將分為兩部分：，其中<<，兩部分的乘積為*()。 *()*()* 因為>*，所以*()>*()*() 又因為>，所以*()>，所以*()>即*()>。從上面的證明可以看出，對于指定的正整數(shù)，如果其大于等于，將它拆分為不同的部分后乘積變大，對于中間結(jié)果也是如此。因此可以將指定的，依次拆成，乘積最大。現(xiàn)在的問題是如何拆分才能保證呢?可以先這樣?。寒敽筒蛔銜r，取，取，取，即從開始按照自然數(shù)的順序取數(shù)，最后剩余的數(shù)給，如果<，此時跟前面的數(shù)字出現(xiàn)了重復(fù)，則把從后

18、面開始平均分布給前面的個數(shù)。為什么要從后面開始往前呢?同樣是考慮數(shù)據(jù)不出現(xiàn)重復(fù)的問題，如果是從前面往后面來平均分配，如加上以后變成，就跟后面的已有的出現(xiàn)了重復(fù)。這樣操作到底是否正確、是否能保證乘積最大呢?還要加以證明。證明過程如下：設(shè)兩個整數(shù)，的和為，且<>，設(shè)，則，*()*()，如果，則，*()*()。的絕對值越小，乘積的常數(shù)項越大，即乘積越大，上面的序列, , , , , 正好滿足了的絕對值最小。但是還要注意兩個特例就是和的情況，它們的分解方案分別為，和，乘積分別為和。以為例，先拆分為：，最后一項為，比小，將其分配給前面的一項，得到，所以最大的乘積為*。以為例，拆分為：，正好是

19、連續(xù)自然數(shù)的和，所以最大乘積為*。再以為例，先拆分為：，因為最后一項為，不比最后第二項大，所以將其平均分給前面的項，優(yōu)先考慮后面的項，即前面的項各分到，笫項分到，最后是，所以最大的乘積為*。由于可能大到，分解之后的各項乘積位數(shù)比較多，超過普通的數(shù)據(jù)類型的位數(shù)，所以要用到高精度運算來進行整數(shù)的乘法運算，將結(jié)果保存在數(shù)組里。本題的貪心策略就是：要使乘積最大，盡可能地將指定的(>)拆分成從開始的連續(xù)的自然數(shù)的和，如果最后有剩余的數(shù)，將這個剩余的數(shù)在優(yōu)先考慮后面項的情況下平均分給前面的各項?；舅惴枋鋈缦拢海ǎ┎鸱诌^程 拆分的數(shù)先?。?當>時做 選擇作為一項； 增加； 減少； ； 如果&

20、gt;，那么將從最后一項開始平均分給各項； 如果還大于，再從最后一項開始分一次；（）求乘積 設(shè)置一個數(shù)組來存放乘積，初始狀態(tài)位數(shù)為，結(jié)果為； 將上面拆分的各項依次跟數(shù)組各項相乘并考慮進位；種樹源程序名 .?（, , ）可執(zhí)行文件名 輸入文件名 輸出文件名 【問題描述】 一條街的一邊有幾座房子。因為環(huán)保原因居民想要在路邊種些樹。路邊的地區(qū)被分割成塊，并被編號成。每個部分為一個單位尺寸大小并最多可種一棵樹。每個居民想在門前種些樹并指定了三個號碼，。這三個數(shù)表示該居民想在和之間最少種棵樹。當然，居民必須記住在指定區(qū)不能種多于區(qū)域地塊數(shù)的樹，所以。居民們想種樹的各自區(qū)域可以交叉。你的任務(wù)是求出能滿足所

21、有要求的最少的樹的數(shù)量。寫一個程序完成以下工作：* 從讀入數(shù)據(jù)* 計算最少要種樹的數(shù)量和位置* 把結(jié)果寫到【輸入】第一行包含數(shù)據(jù)，區(qū)域的個數(shù)(<)；第二行包含，房子的數(shù)目(<)；下面的行描述居民們的需要： ，<，?！据敵觥枯敵鑫募谝恍袑懹袠涞臄?shù)目，下面的行包括所有樹的位置，相鄰兩數(shù)之間用一個空格隔開?！緲永俊舅惴ǚ治觥?不難想到下面的貪心算法：按照每個區(qū)間的右端點排序，從左向右掃描，把每個區(qū)間內(nèi)的樹都盡量種在該區(qū)間的右端，由于后一個區(qū)間的右端不在這個區(qū)間的右端的左邊(排序)，可以保證這些樹盡可能多地被下面的區(qū)間利用到。 掃描需要的時間為()，更新需要的時間為()，所以總的

22、時間復(fù)雜度為(*)。餐巾源程序名 .?（, , ）可執(zhí)行文件名 輸入文件名 輸出文件名 【問題描述】 一個餐廳在相繼的天里，第天需要塊餐巾(，)。餐廳可以從三種途徑獲得餐巾。 ()購買新的餐巾，每塊需分； ()把用過的餐巾送到快洗部，洗一塊需天，費用需分(<)。如時，第一天送到快洗部的餐巾第二天就可以使用了，送慢洗的情況也如此。 ()把餐巾送到慢洗部，洗一塊需天(>)，費用需分(<)。 在每天結(jié)束時，餐廳必須決定多少塊用過的餐巾送到快洗部，多少塊送慢洗部。在每天開始時，餐廳必須決定是否購買新餐巾及多少，使洗好的和新購的餐巾之和滿足當天的需求量，并使天總的費用最小。【輸入】 輸

23、入文件共行，第行為總天數(shù)；第行為每天所需的餐巾塊數(shù)；第行為每塊餐巾的新購費用，快洗所需天數(shù)，快洗所需費用，慢洗所需天數(shù)，慢洗所需費用?！据敵觥?輸出文件共行。第行為最小的費用。下面的行為從第天開始每天需要的總餐巾數(shù)、需購買的新餐巾數(shù)、結(jié)束時往快、慢洗部送洗的餐巾數(shù)以及用到的來自快洗的餐巾數(shù)和來自慢洗的餐巾數(shù)。【樣例】【算法分析】 在思考這個問題時，一般容易想到從洗的角度去思考，這就必然要對每天的餐巾來源進行分類窮舉，當天數(shù)較長，每天需求量較大時，窮舉的數(shù)量級至少為每天的餐巾數(shù)之積，程序很難在規(guī)定時間內(nèi)運行出最優(yōu)解。如果從買的角度去思考這個問題，則該問題就變得十分簡單。在確定要買的餐巾數(shù)之后，顯

24、然這些餐巾購買得越早，被反復(fù)利用的可能就越大。也就是說，這些餐巾必須在最早的幾天中購買，余下的缺口用洗出來的餐巾來填補，對每天用下來的餐巾，假設(shè)全部都送洗，但送洗時不確定其狀態(tài)，即它們有可能被快洗，有可能被慢洗，也可能不用洗，其狀態(tài)在今后被選用時再確定。在確定每天的需求時，除去買的，剩下的首先要選用慢洗為好。這種餐巾有多少應(yīng)用多少，不夠再選用快洗出來的餐巾。選用快洗出來的餐巾時，應(yīng)選用最近的若干天中才快洗出來的餐巾，這樣可以保證有更多的餐巾被慢洗出來。這就是我們的貪心思想。對所要購買的餐巾數(shù)進行窮舉，開始時其值為所需用餐巾數(shù)之和，當購買量太少而周轉(zhuǎn)不過來時，程序結(jié)束。在確定了購買的餐巾總數(shù)后，

25、按上述算法構(gòu)造出最小費用方案，所有的最小費用方案中的最優(yōu)解即為問題的解。程序(見本書光盤)中數(shù)組存放每天需用的餐巾數(shù)，數(shù)組記錄每天來自慢洗的餐巾數(shù)。數(shù)組記錄每天來自快洗的餐巾數(shù)，數(shù)組記錄每天購買的餐巾數(shù)。變量存儲當天可供選用的已經(jīng)慢洗好的餐巾數(shù)。這個算法的數(shù)量級為()，其中為所有天中需用的餐巾數(shù)之總和。馬拉松接力賽源程序名 .?（, , ）可執(zhí)行文件名 輸入文件名 輸出文件名 【問題描述】某城市冬季舉辦環(huán)城馬拉松接力賽，每個代表隊有人參加比賽，比賽要求每個的每名參賽選手只能跑一次，一次至少跑、最多只能跑，而且每個選手所跑的公里數(shù)必須為整數(shù)，即接力的地方在整公里處。 劉老師作為學(xué)校代表隊的教練，

26、精心選擇了名長跑能手，進行了訓(xùn)練和測試，得到了這名選手盡力連續(xù)跑、的所用時間?，F(xiàn)在他要進行一個合理的安排，讓每個選手跑合適的公里數(shù)，使學(xué)校代表隊跑完所用的時間最短。根據(jù)隊員的情況，這個最短的時間是惟一的，但安排方案可能并不惟一。根據(jù)測試情況及一般運動員的情況得知，連續(xù)跑要比連續(xù)跑速度快，連續(xù)跑又要比連續(xù)跑速度快也就是說連續(xù)跑的路程越長，速度越慢，當然也有特殊的，就是速度不會變慢，但是絕不可能變快?！据斎搿啃袛?shù)據(jù)，分別是到號隊員的測試數(shù)據(jù)，每行的個整數(shù)，表示某一個運動員盡力連續(xù)跑、所用的時間。【輸出】兩行，第一行是最短的時間，第二行是五個數(shù)據(jù)，分別是到號隊員各自連續(xù)跑的公里數(shù)。【樣例】【算法分析

27、】 初看此題，好象是一個排列問題，選取個之間的數(shù)，共有*種情況，對每一種情況，再看其和是否為，在和為的情況下再計算所用的總時間，找出其中最少的。 這種枚舉的方法，肯定能找到最優(yōu)解，但是這樣做的效率不高，執(zhí)行時間長，這里是個選手還行，如果更多，如個選手，就要對種可能情況進行判定，再快的計算機也要較長的時間來執(zhí)行。 因為運動員連續(xù)跑一公里要比連續(xù)跑兩公里速度快、連續(xù)跑兩公里又要比連續(xù)跑三公里速度快也就是說連續(xù)跑的路程越長，速度越慢，所以我們可以將每個選手的所跑時間進行分段處理，計算出各自所跑每一公里所用的時間。又因為要求每個選手至少跑一公里，先給每一個人分配一公里。剩下的里程由哪個選手來跑呢?這時

28、檢查各自所跑第二公里所用的時間，哪個用的時間最短就選這個選手繼續(xù)跑一公里，因為這樣做可以保證當前所用的時間最少，這個所手所跑的公里數(shù)增加。下一公里繼續(xù)用這種方法選，看當前要跑一公里哪個用的時間最短就選誰，選了誰，誰所跑的公里數(shù)增加，下面要檢查的時間段就是他的下一段如此反復(fù)直到公里分配完為止。 對于每個運動員跑各公里所用的時間不一定要單獨計算出來，如它跑第公里所用的時間等于他連續(xù)跑完公里所用的時間減去他連續(xù)跑公里所用的時間。 本題所用的貪心策略就是： 先分配每個運動員跑一公里；剩下的公里始終選擇所有運動員當中下一公里跑的時間最短的，直到分配完。 這樣局部的最優(yōu)保證整體的最優(yōu)。線性存儲問題源程序名

29、 .?（, , ）可執(zhí)行文件名 輸入文件名 輸出文件名 【問題描述】 磁帶等存儲介質(zhì)存儲信息時基本上都是一種線性存儲的方式，線性存儲方式雖然簡單，但查詢檢索時往往要經(jīng)過一些其它信息，不象磁盤等存儲介質(zhì)在目錄區(qū)找到后可直接定位到某一區(qū)城，因此線性存儲總有它的局限性。但是由于磁帶等線性存儲有簡單、保存時間相對較長等優(yōu)點，現(xiàn)在仍然在使用。 如果有段信息資料要線性存儲在某種存儲介質(zhì)上，它們的長度分別是，存儲介質(zhì)能夠保存下所有這些信息，假設(shè)它們的使用(查詢檢索)的頻率分別是，要如何存儲這些信息資料才能使平均檢索時間最短。你的任務(wù)就是編程安排一種平均檢索時間最短的方案?！据斎搿?第一行是一個正整數(shù)(<)，接下來是行數(shù)據(jù)，每行兩個整數(shù)分別是第段信息的長度(到之