《花生采摘》解題報(bào)告.doc
《《花生采摘》解題報(bào)告.doc》由會(huì)員分享,可在線(xiàn)閱讀,更多相關(guān)《《花生采摘》解題報(bào)告.doc(5頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
《花生采摘》解題報(bào)告 By sx349 【摘要】 核心算法思想:貪心 主要數(shù)據(jù)結(jié)構(gòu): 其他輔助知識(shí): 時(shí)間復(fù)雜度: 空間復(fù)雜度: 【題目大意】 給定一個(gè)非空矩陣,每次都從中選擇一個(gè)最大值并將其從矩陣中排除,將這些取出的數(shù)排序后計(jì)算其花費(fèi)(相鄰兩數(shù)的花費(fèi)是其在矩陣之間的曼哈頓距離),求在給定最大花費(fèi)下,能取到的最大值的最大總和。 【算法分析】 文中說(shuō)道:“你先找出花生最多的植株,去采摘它的花生;然后再找出剩下的植株里花生最多的,去采摘它的花生;依此類(lèi)推,不過(guò)你一定要在我限定的時(shí)間內(nèi)回到路邊?!? 根據(jù)這一句話(huà),我們直接就可以得出,這道題應(yīng)該采用貪心的算法。 因此,我們先對(duì)數(shù)據(jù)進(jìn)行從大到小的排序,然后每次都取其中的最大值。因?yàn)楸仨氃谝?guī)定的時(shí)間內(nèi)回到路邊,所以在每次取最大值時(shí),首先判斷在采摘了這一次之后是否有足夠的時(shí)間回到路邊,即(去采摘目標(biāo)花生的時(shí)間)+(采摘那目標(biāo)花生所用的1單位時(shí)間)+(從目標(biāo)所在地往第一行的時(shí)間)<=(剩下的單位時(shí)間)。若條件不滿(mǎn)足就停止,若滿(mǎn)足就繼續(xù)采摘。 由于去摘花生必須從路邊進(jìn)入花生田和從花生田出來(lái),所以我們可以先減去2個(gè)單位時(shí)間,再將剩下的時(shí)間進(jìn)行模擬。 【心得體會(huì)】 花生采摘是一道典型的貪心問(wèn)題,也是一道典型的簡(jiǎn)單題(因此這道題的算法分析也只能這樣簡(jiǎn)單了……)。但是這道題有一個(gè)區(qū)別于其他問(wèn)題的地方:在解決問(wèn)題的過(guò)程中,主要部分(連續(xù)取最大值)的時(shí)間復(fù)雜度只需要,而排序卻花費(fèi)了的時(shí)間復(fù)雜度。 這一點(diǎn)確實(shí)是在許多情況下無(wú)法回避的一個(gè)問(wèn)題。我一直記得我們平時(shí)上課的計(jì)算機(jī)書(shū)上有一個(gè)簡(jiǎn)單的例子:給你一些電話(huà)號(hào)碼,讓你去尋找某一個(gè)指定的號(hào)碼。書(shū)上的解釋是用二分查找,但是我們來(lái)考慮一下,二分查找合適嗎?當(dāng)然,如果是在有序的情況下,二分的復(fù)雜度是,但是,在無(wú)序的情況下,二分必須要在排序好后才能解決,那么時(shí)間復(fù)雜度就上升到了,因?yàn)槌松俨糠痔厥獾呐判蛑?,因此不可避免地?dǎo)致了的排序復(fù)雜度。如此一來(lái),就超過(guò)了順序查找的復(fù)雜度了。難道排序的合理性就此受到了質(zhì)疑了嗎?當(dāng)然不是,如果是查找多次的話(huà),二分查找的時(shí)間復(fù)雜度就是,而順序查找則飆升到了。由此我們可以得出這樣一個(gè)結(jié)論:預(yù)處理操作的效率隨著預(yù)處理所得到的數(shù)據(jù)的使用率的提高而提高。 這又引出了這樣一個(gè)怪異的想法:如果我找到了針對(duì)某個(gè)問(wèn)題的一個(gè)時(shí)間復(fù)雜度僅為的主算法,那么我是不是就一定能解決它呢?顯然不是。如果這個(gè)問(wèn)題的輸入達(dá)到了上千萬(wàn)乃至上億,單單讀入的復(fù)雜度就已經(jīng)使程序罷工了。同樣的,我也曾經(jīng)有過(guò)因?yàn)檩敵鲞^(guò)多而導(dǎo)致超時(shí)的經(jīng)歷。 因此,輸入、輸出、排序乃至其他一些游離于主算法之外的東西,有時(shí)反而成為了一個(gè)問(wèn)題的決定點(diǎn),這種出人意料的場(chǎng)景也著實(shí)是值得我們思考的。 【附錄】 2005選拔賽第一輪 花生采摘 peanuts.pas/dpr/c/cpp 輸入文件名:peanuts .in 輸出文件名:peanuts.ou 【問(wèn)題描述 】 魯濱遜先生有一只寵物猴,名叫多多。這天,他們兩個(gè)正沿著鄉(xiāng)間小路散步,突然發(fā)現(xiàn)路邊的告示牌上貼著一張小小的紙條:“歡迎免費(fèi)品嘗我種的花生!——熊字”。 魯濱遜先生和多多都很開(kāi)心,因?yàn)榛ㄉ撬麄兊淖類(lèi)?ài)。在告示牌背后,路邊真的有一塊花生田,花生植株整齊地排列成矩形網(wǎng)絡(luò)(如圖1)。有經(jīng)驗(yàn)的多多一眼就能看出,每株花生植株下的花生有多少。 為了訓(xùn)練多多的算術(shù),魯濱遜先生說(shuō):“你先找出花生最多的植株,去采摘它的花生;然后再找出剩下的植株里花生最多的,去采摘它的花生;依此類(lèi)推,不過(guò)你一定要在我限定的時(shí)間內(nèi)回到路邊?!? 2 4 6 5 1 3 7 1 3 4 6 2 5 路 圖1 2 4 6 5 1 3 7 1 3 4 6 2 5 路 圖2 15 13 7 9 我們假定多多在每個(gè)單位時(shí)間內(nèi),可以做下列四件事情中的一件: 1) 從路邊跳到最靠近路邊(即第一行)的某棵花生植株; 2) 從一棵植株跳到前后左右與之相鄰的另一棵植株; 3) 采摘一棵植株下的花生; 4) 從最靠近路邊(即第一行)的某棵花生植株跳回到路邊。 現(xiàn)在給定一塊花生田的大小和花生的分布,請(qǐng)問(wèn)在限定的時(shí)間內(nèi),多多最多可以采到多少個(gè)花生?注意可能只有部分的植株下面長(zhǎng)有花生,假設(shè)這些植株下的花生個(gè)數(shù)各不相同。 例如在圖二所示的花生田里,只有位于(2,5),(3,7),(4,2),(5,4)的植株下長(zhǎng)有花生,個(gè)數(shù)分別為13,7,15,9。沿著圖示的路線(xiàn),多多在21個(gè)單位時(shí)間內(nèi),最多可以采到37個(gè)花生。 [輸入文件] 輸入文件peanuts.in的第一行包括三個(gè)整數(shù),M,N和K,用空格隔開(kāi);表示花生田的大小為M*N(1<=M,N<=20),多多采花生的限定時(shí)間為K(0<=K<=1000)個(gè)單位時(shí)間. 接下來(lái)的M行,每行包括N個(gè)非負(fù)整數(shù),也用空格隔開(kāi); 第i+1行的第j個(gè)整數(shù)Pij(0<=Pij<=500)表示花生田里植株(i,j)下花生的數(shù)目,0表示該植株下沒(méi)有花生。 [輸出文件] 輸出文件peanuts.out包括一行. 這一行只包含一個(gè)整數(shù),即在限定時(shí)間內(nèi),多多最多可以采到的花生的個(gè)數(shù)。 [樣例輸入] 6 7 21 0 0 0 0 0 0 0 0 0 0 0 13 0 0 0 0 0 0 0 0 7 0 15 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 [樣例輸出1] 37 [樣例輸入2] 6 7 20 0 0 0 0 0 0 0 0 0 0 0 13 0 0 0 0 0 0 0 0 7 0 15 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 [樣例輸出2] 28 【源程序清單】 { PROG: Peanuts LANG: PASCAL ID: xyj-flash } Program Peanuts; Var X,Y,Value:Array[0.400] of Longint; Map:Array[1..20,1..20] of Longint; M,N,K,I,J,Top,T,Sum:Longint; Procedure Sort(L,R:Longint); Var I,J,Mid:Longint; Begin I:=L;J:=R;Mid:=Value[(L+R) Div 2]; Repeat While Value[I]>Mid do Inc(I); While Value[J]- 1.請(qǐng)仔細(xì)閱讀文檔,確保文檔完整性,對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來(lái)的問(wèn)題本站不予受理。
- 2.下載的文檔,不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請(qǐng)點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
9.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁(yè)顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開(kāi)word文檔。
- 特殊限制:
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 花生采摘 花生 采摘 解題 報(bào)告
鏈接地址:http://www.hcyjhs8.com/p-9389589.html