貪心法習(xí)題匯總

《貪心法習(xí)題匯總》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)。

1、貪心法習(xí)題匯總貪心法習(xí)題匯總3.1排隊(duì)接水源程序名water.???（pas,c,cpp）可執(zhí)行文件名water.exe輸入文件名water.in輸出文件名water.out【問(wèn)題描述】有n個(gè)人在一個(gè)水龍頭前排隊(duì)接水，假如每個(gè)人接水的時(shí)間為T(mén)i，請(qǐng)編程找出這n個(gè)人排隊(duì)的一種順序，使得n個(gè)人的平均等待時(shí)間最小。【輸入】輸入文件共兩行，第一行為n；第二行分別表示第1個(gè)人到第n個(gè)人每人的接水時(shí)間T1，T2，…，Tn，每個(gè)數(shù)據(jù)之間有1個(gè)空格?！据敵觥枯敵鑫募袃尚?，第一行為一種排隊(duì)順序，即1到n的一種排列；第二行為這種排列方案

2、下的平均等待時(shí)間(輸出結(jié)果精確到小數(shù)點(diǎn)后兩位)?！緲永縲ater.inwater.out103278149610556121991000234335599812291.90【算法分析】平均等待時(shí)間是每個(gè)人的等待時(shí)間之和再除以n，因?yàn)閚是一個(gè)常數(shù)，所以等待時(shí)間之和最小，也就是平均等待時(shí)間最小。假設(shè)是按照1~n的自然順序排列的，則這個(gè)問(wèn)題就是求以下公式的最小值：如果用窮舉的方法求解，就需要我們產(chǎn)生n個(gè)人的所有不同排列，然后計(jì)算每種排列所需要等待的時(shí)間之和，再“打擂臺(tái)”得到最小值，但這種方法需要進(jìn)行n!次求和以及判斷，時(shí)間

3、復(fù)雜度很差！其實(shí)，我們認(rèn)真研究一下上面的公式，發(fā)現(xiàn)可以改寫(xiě)成如下形式：這個(gè)公式何時(shí)取最小值呢？對(duì)于任意一種排列k1,k2,k3,…,kn，當(dāng)≤≤≤…≤時(shí)，total取到最小值。如何證明呢？方法如下：因?yàn)榧僭O(shè)i

4、成：把n個(gè)等待時(shí)間按非遞減順序排列，輸出這種排列，并求出這種排列下的平均等待時(shí)間。17/17貪心法習(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)檫@些錢(qián)還不一定都是你的？！接下來(lái)主持人宣布了比賽規(guī)則：首先，比賽時(shí)間分為n個(gè)時(shí)段(n≤500)，它又給出了很多小游戲

5、，每個(gè)小游戲都必須在規(guī)定期限ti前完成(1≤ti≤n)。如果一個(gè)游戲沒(méi)能在規(guī)定期限前完成，則要從獎(jiǎng)勵(lì)費(fèi)m元中扣去一部分錢(qián)wi，wi為自然數(shù)，不同的游戲扣去的錢(qián)是不一樣的。當(dāng)然，每個(gè)游戲本身都很簡(jiǎn)單，保證每個(gè)參賽者都能在一個(gè)時(shí)段內(nèi)完成，而且都必須從整時(shí)段開(kāi)始。主持人只是想考考每個(gè)參賽者如何安排組織自己做游戲的順序。作為參賽者，小偉很想贏(yíng)得冠軍，當(dāng)然更想贏(yíng)取最多的錢(qián)！注意：比賽絕對(duì)不會(huì)讓參賽者賠錢(qián)!【輸入】輸入文件riddle.in，共4行。第1行為m，表示一開(kāi)始獎(jiǎng)勵(lì)給每位參賽者的錢(qián)；第2行為n，表示有n個(gè)小游戲；第3行有

6、n個(gè)數(shù)，分別表示游戲1到n的規(guī)定完成期限；第4行有n個(gè)數(shù)，分別表示游戲1到n不能在規(guī)定期限前完成的扣款數(shù)?！据敵觥枯敵鑫募iddle.out，僅1行。表示小偉能贏(yíng)取最多的錢(qián)?！緲永縭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)行放置。假如罰款最

7、多的一個(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í)段，

8、挑出一個(gè)最小的去掉并累加扣款值，然后再去調(diào)整排列順序，讓后面的元素填補(bǔ)前面的空缺，具體實(shí)現(xiàn)請(qǐng)看下面的參考程序2。17/17貪心法習(xí)題匯總3.3取火柴游戲源程序名match.???（pas,c,cpp）可執(zhí)行文件名match.exe輸入文件名match.in輸出文件名match.out【問(wèn)題描述】輸入k及k個(gè)整數(shù)n1，n2，…，nk