《《花生采摘》解題報(bào)告.doc》由會(huì)員分享，可在線閱讀，更多相關(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ù)這一句話，我們直接就可以得出，這道題應(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)單的例子：給你一些電話號(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)然不是，如果是查找多次的話，二分查找的時(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。沿著圖示的路線，多多在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]J; If I0 Then Begin Inc(Top); Value[Top]:=Map[I,J]; X[Top]:=I;Y[Top]:=J; End; End; Sort(1,Top); K:=K-2; X[0]:=1;Y[0]:=Y[1]; T:=0;I:=1;Sum:=0; While TK Then Print(Sum); Sum:=Sum+Value[I]; T:=T+X[I]-1; Inc(I); End; End.